I already found interesting answers in other questions to this topic. Yet, I still don't get it well enough to use it. Can someone please show it with an example? I won't tell you mine, because it's a homework and I really want to understand it myself.
How to use modulo to find the last character of an exponentiation?
-
0And I will post my result, when I understood it $a$nd c$a$lculated the result, okay? – 2012-01-22
2 Answers
For $a^N\equiv x\pmod{10}$ (with $0\leq x<10$), a general strategy is to start finding a small exponent $n$ such that $a^n\equiv 0,1,-1\pmod{10}$.
Example 1: $3^{1000}\equiv x\pmod{10}$. We have $3^2\equiv -1\pmod{10}$ thus $3^4=(3^2)^2\equiv (-1)^2\equiv 1\pmod{10}$, then $3^{1000}=(3^4)^{250}\equiv 1^{250}\equiv 1\pmod{10}$.
Example $1+\epsilon$: $3^{1001}\equiv x\pmod{10}$. Then $3^{1001}=3.3^{1000}\equiv 3.1\equiv3\pmod{10}$.
Example 2: sometimes, we cannot follow this strategy as in this example. $2^{1000}\equiv x\pmod{10}.$
$ 2^3\equiv -2\pmod{10}\quad\textrm{thus}\quad 2^9=(2^3)^3\equiv (-2)^3=-2^3\equiv 2 \pmod{10}. $ Then $ 2^{1000}=2.2^{999}=2.(2^9)^{111}\equiv2.2^{111}=2^{112}=2^4.(2^9)^{12}\equiv 2^4.2^12=2^{16}\pmod{10}, $ finally $ 2^{1000}\equiv 2^7.2^9\equiv 128.2\equiv -4\equiv 6\pmod{10}. $
-
1I think you should try with an example, like $13^{1000}$. Let me know if you have any problem. – 2012-01-22
Suppose that you want to find last digit of number : $7^{202}$
First , note that according to the Euler's theorem it follows that :
$7^{\phi(10)} \equiv 1 \pmod {10} \Rightarrow 7^4 \equiv 1 \pmod {10}$
Now write $7^{202}$ as :
$7^{202}= 7^2 \cdot(7^4)^{50}$
Since $7^2=49 \equiv 9 \pmod{10}$ and $(7^4)^{50} \equiv 1 \pmod {10}$ we get :
$7^{202} \equiv 9 \pmod {10}$ , therefore last digit in this example is $9$ .
-
0This works when $a$ is coprime to $10$. It's the best way to find an $n$ such that $a^n\equiv 1\pmod{10}.$ – 2012-01-22