2
$\begingroup$

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}$.

$\endgroup$
3
$\begingroup$

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$.

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

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*} $$

$\endgroup$
2
$\begingroup$

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)$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.