Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

4 Answers 4

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

share|improve this answer
1  
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*} $$

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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