# using Fermat's little theorem to reduce a large number mod a prime

i want to show that $2^{70}\equiv 10 \pmod{13}$ using Fermat's little theorem. I see that $2^{12}\equiv 1 \pmod{13}$ hence $2^{60}\equiv 1 \pmod{13}$ so $2^{70}\equiv 2^{10} \pmod{13}$ but i don't see how to finish this without evaluating $2^{10}$.

-

What's so bad about evaluating $2^{10}$ modulo $13$? I can do it without help of pencil and paper: $2^4=16\equiv 3$ so $2^5\equiv2\times3=6$ and $2^{10}=(2^5)^2\equiv6^2=36\equiv10$ all modulo $13$. Or you could use $2^{72}\equiv1$ so $2^{70}\equiv2^{-2}=7^2$ since $7=\frac{13+1}2$ is the inverse of $2$ modulo $13$.

-
you mean $2^{-2}=7^2$ since $7*2\equiv 1 \pmod{13}$ –  palio Mar 2 '12 at 10:10
Yep, thanks; I think I caught the smell of the answer too soon. Corrected now. –  Marc van Leeuwen Mar 2 '12 at 11:27

If you look at the powers of $2$ modulo $13$, for all even powers as say

\begin{align*} 2^2 &= 4 \equiv 4 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^4 &= 2^2 \times 2^2 \equiv 4 \times 4 = 3 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^6 &= 2^4 \times 2^2 \equiv 12 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^8 &= 2^6 \times 2^2 \equiv 12 \times 4 = 48 = 9 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{10} &= 2^8 \times 2^2 \equiv 9 \times 4 = 36 = 10 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{12} &= 2^{10} \times 2^2 \equiv 10 \times 4 = 40 = 1 \hspace{4pt}(\mod 13\hspace{4pt})\\ \\ 2^{14} &= 2^{12} \times 2^2 \equiv 1 \times 4 = 4 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{16} &= 2^{14} \times 2^2 \equiv 4 \times 4 = 16 = 3 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{18} &= 2^{16} \times 2^2 \equiv 12 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{20} &= 2^{18} \times 2^2 \equiv 12 \times 4 = 48 = 9 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{22} &= 2^{20} \times 2^2 \equiv 9 \times 4 = 36 = 10 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{24} &= 2^{22} \times 2^2 \equiv 10 \times 4 = 40 = 1 \hspace{4pt}(\mod 13\hspace{4pt})\\ \end{align*}

The values cycle in terms of powers as multiples of $12$ as $1\hspace{4pt}(\mod 13\hspace{4pt})$

If you follow this pattern, $2^{60} \equiv 1 \hspace{4pt}(\mod 13\hspace{4pt})$ and further

\begin{align*} 2^{62} &= 2^{60} \times 2^{2} \equiv 4 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{64} &= 2^{62} \times 2^2 \equiv 4 \times 4 = 3 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{64} &= 2^{62} \times 2^2 \equiv 12 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{68} &= 2^{64} \times 2^2 \equiv 12 \times 4 = 48 = 9 \hspace{4pt}(\mod 13\hspace{4pt})\\ 2^{70} &= 2^{68} \times 2^2 \equiv 9 \times 4 = 36 = 10 \hspace{4pt}(\mod 13\hspace{4pt})\\ \end{align*}

-

Hint $\$ By little Fermat$\rm\ \ 2^{12}\equiv 1\ \Rightarrow\ 2^{72}\equiv 1\ \Rightarrow\ 2^{70}\equiv \dfrac{1}{2^2}\equiv\: \dfrac{-12}4 \equiv -3\pmod{13}$

More generally, one can easily invert any factor of modulus $\!\pm 1$ $$\rm M = AB\mp 1\ \ \Rightarrow\ \ A^{\:\!-1\:+\:K\:\phi(M)}\:\equiv\: A^{-1}\:\equiv\: \pm B\ \ (mod\ M)$$

-

At some point in these things it is obvious that you are going to have to do some kind of calculaton, not every power is evenly divisible by $12$.

However it IS clear that in the end you will always get a power inbetween $0$ and $11$. These can be worked out easily by taking it one step at a time and reducing along the way...you will NOT have to work out the value of $2^{10}$ here but it is enough to work out say $2^5$, reduce mod $13$ and then square the answer.

-