Question

Use Fermat’s little theorem to find${23}^{1002}mod41$

Short answer

Using the Fermat’s little theorem,

${23}^{1002}mod41$

Step-by-step solution

Step 1

Given

${23}^{1002}mod41$

Fermat’s little theorem role="math" localid="1668656591675" $a^{p-1}\equiv (modp)$state if $p$is prime and $a$not divisible by$p$

When $a=23$and$p=41$, Fermat’s little theorem then implies

${23}^{40}={23}^{41-1}\equiv 1(mod41)$

Step 2

Since$1002=1000+2=25.40+2$

$$\begin{gathered} {23}^{1002}mod41-{23}^{40.25+2}mod41 \\ =\left({23}^{40.25}\cdot {23}^2\right)mod41 \\ =\left(\left({23}^{40.25}mod41\right)\cdot \left({23}^{2}mod41\right)\right)mod41 \\ \left.=\left({\left({23}^{40}\right)}^{25}mod41\right)\cdot (529mod41)\right)mod41 \\ -\left(\left((1{)}^{25}mod41\right)\cdot 37\right)mod41 \\ =\left(1.37\right)mod41 \\ \begin{array}{r}=37mod41\\ =37\end{array} \end{gathered}$$