Question

a) use Fermat’s little theorem to compute$3^{302}mod5$and$3^{302}mod7,3^{302}mod11$.

b) Use your results from part (a) and the Chinese remainder theorem to find $3^{302}mod385$. (Note that$385=\mathrm{5.7.11}$)

Short answer

$$\begin{gathered} a)4,2,9 \\ b)9 \end{gathered}$$

Step-by-step solution

Step 1

a) By Fermat’s little theorem (FLT) states that $a^{p-1}\equiv 1(modp)$if $a$and$p$are relatively prime. So by the FLT,$3^4\equiv 1(mod5),3^6\equiv 1(mod7)\text{and}{3}^{10}\equiv 1(mod11)$. Using these congruence, we can evaluate the required congruence as follows.

$\begin{array}{r}{3}^{302}\equiv {\left(3^4\right)}^{75}\cdot 3^2(mod5)\\ \equiv 1.9(mod5)\\ \equiv 9(mod5)\\ \equiv 4(mod5)\end{array}$

$\begin{array}{r}{3}^{302}\equiv {\left(3^6\right)}^{30}\cdot 3^2(mod7)\\ \equiv 1.9(mod7)\\ \equiv 9(mod7)\\ \equiv 2(mod7)\end{array}$

$\begin{array}{r}{3}^{302}\equiv {\left(3^{10}\right)}^{30}\cdot 3^2(mod11)\\ \equiv 1.9(mod11)\\ \equiv 9(mod11)\end{array}$

Step 2

b) since$3^{302}\equiv 9(mod5),3^{302}\equiv 9(mod7)$and$3^{302}\equiv 9(mod11)$by the Chinese remainder theorem. Since$5.7.11=385,3^{302}\equiv 9(mod385)$