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?
-
1_Especially_ when it is homework, it is important that you show some work of your own. Just stating "I won't tell you mine" is not going to cut it. – 2012-01-22
-
1Also, I think that when you write "character" you mean "digit". – 2012-01-22
-
0@Henning: Thanks for stating what you are missing. I have no idea at all. If you ask someone to add 2 numbers without explaining how to add, what can he show then? The only thing I could do was researching the internet. I did and showed some research results. Sorry, couldn't deliver more. – 2012-01-22
-
0And I will post my result, when I understood it and calculated 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}.
$$
-
0@erikb: tell me if you want an other explicit example. As an example 2, sometimes we have to find other strategies. – 2012-01-22
-
0It is more detailed, but still I don't understand it. I.e. how can you say something is ≡ -1, if -1 is not in N. And why do you do this step in the first place? And in example 2, why not 2^2? – 2012-01-22
-
0About your first question: $-1\equiv 9\pmod{10}$, e.g. $3^2\equiv -1\pmod{10}$. – 2012-01-22
-
1Second: when you obtain that $a^n\equiv 0,1,-1\pmod{10}$, the rest is easy. In the Example 2, make $2^2=4\pmod{10}$ doesn't help because the last digit is not "near" to $0$. We need that $a^n\pmod{10}$ equals $0,1,-1$ or (at the worst of cases) the same number $a$. Thus we began with $2^3$ at Example 2. – 2012-01-22
-
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