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.

Let $n$ be an even integer not divisible by $10$, what digit is in the $10$s place for $n^{20}$ and the hundreds place for $n^{200}$, can you generalise this?

I know that for $n^{20}$ they end in $76$ and for $n^{200}$ they all end in $376$ I even went on too see that $n^{2000}$ always ends in $9376$.

I was given a clue that $76$ is the only number that is divisible by $4$ that gives $1$ when working $\bmod{25}$, I'm not sure how to relate that and generalise

When working $\bmod{100}$ for $n^{20}$ I noticed, $100 = 4 \times 25 = 2^2 \times 5^2$ , so we looked at a number divisible by $4$ that gave $1$ when working in $\bmod{25}$.

Similarly for $n^{200}$, $1000 = 2^3 \times 5^3$, for which $376$ is divisible by $8$ and gives $1$ when working with $\bmod{125}$?

Am I looking along the right lines?

Any help would be greatly appreciated.

Thanks!

share|improve this question
    
See also this related answer. –  Math Gems Feb 5 '13 at 21:09

1 Answer 1

up vote 3 down vote accepted

Let us first do the case $n^{20} \pmod{100}$.

You have been advised to split this into two problems

  • $n^{20} \pmod{4}$. Since $n$ is even, this yields $n^{20} \equiv 0 \pmod{4}$ here.
  • $n^{20} \pmod{25}$. Since $n$ is not divisible by $5$, we have $(n, 25) = 1$. Since $\varphi(25) = 20$, we obtain $n^{20} \equiv 1 \pmod{25}$.

(Here $\varphi$ is Euler's totient function.)

Now you solve the system of congruences $$ \begin{cases} x \equiv 0 \pmod{4}\\ x \equiv 1 \pmod{25} \end{cases} $$ which has the solution(s) $x \equiv 76 \pmod{100}$.

In the general case $k \ge 2$ you have $n^{2 \cdot 10^{k-1}} \pmod{10^{k}}$. Again, split it into two problems

  • $n^{2 \cdot 10^{k-1}} \equiv 0 \pmod{2^k}$, as above.
  • $n^{2 \cdot 10^{k-1}} \pmod{5^k}$. Since $n$ is not divisible by $5$, we have $(n, 5^k) = 1$. Since $\varphi(5^k) = 5^k - 5^{k-1} = 4 \cdot 5^{k-1}$, we obtain $n^{2 \cdot 10^{k-1}} \equiv 1 \pmod{5^k}$.

Now you solve the system of congruences $$ \begin{cases} x \equiv 0 \pmod{2^k}\\ x \equiv 1 \pmod{5^k}. \end{cases} $$

share|improve this answer
    
Please excuse my ignorance but what exactly is φ(x) ? –  user61067 Feb 5 '13 at 12:28
    
@user61067, it's Euler's totient function, I have added a link in the answer. –  Andreas Caranti Feb 5 '13 at 12:30
    
Got it, thank you for all your help –  user61067 Feb 5 '13 at 12:33
    
@user61067, you're welcome! –  Andreas Caranti Feb 5 '13 at 12:38
    
Sorry, just to confirm, what do you mean when you say 'Since n is not divisible by 5, we have (n,25)=1' –  user61067 Feb 5 '13 at 12:43

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.