Question

Use Fermat’s little theorem to find $7^{121}mod13$

Short answer

Using the Fermat’s little theorem,

$7^{121}mod13$

Step-by-step solution

Step 1

Given

$7^{121}mod13$

Fermat’s little theorem states$a^{p-1}\equiv (modp)$if $p$is prime and $a$not divisible by

When $a=7$and$p=13$, Fermat’s little theorem then implies

$7^{12}=7^{13-1}\equiv 1(mod13)$

Step 2

since$121=120+1=12\cdot 10+1$

$$\begin{gathered} 7^{121}mod13=7^{12\cdot 10+1}mod13 \\ =\left(7^{12.10}\cdot 7\right)mod13 \\ =\left(\left(7^{12,10}mod13\right)\cdot (7mod13)\right)mod13 \\ -\left(\right(\left(1\right)mod13\left).7\right)mod13 \\ =\left(1.7\right)mod13 \\ \begin{array}{r}=7mod13\\ -7\end{array} \end{gathered}$$