1
$\begingroup$

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.

  • 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
  • 1
    Also, 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
  • 0
    And I will post my result, when I understood it and calculated the result, okay?2012-01-22

2 Answers 2

4

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
  • 0
    It 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
  • 0
    About your first question: $-1\equiv 9\pmod{10}$, e.g. $3^2\equiv -1\pmod{10}$.2012-01-22
  • 1
    Second: 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
  • 1
    I think you should try with an example, like $13^{1000}$. Let me know if you have any problem.2012-01-22
1

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

  • 0
    This 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