Number theory - congruence

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!

-
See also this related answer. – Math Gems Feb 5 '13 at 21:09

1 Answer

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

-
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