Every positive power of $5$ appears in the last digits of bigger power of $5$

Question

Problem. Show that for every positive integer $n$, there is an integer $N > n$ such that the number $5^n$ appears as the last few digits $5^N$. For example, if $n = 3$, we have $5^3 = 125$ and $5^5 = 3125$, so $N = 5$ would satisfy.

This is a problem from the worksheet of the class Putnam Seminar at CMU. Please give hints towards the right direction and not the full solutions. Thanks!!

Answer 1

Fix $n$. The cases $n \le 3$ can be handled directly. We now assume $n > 3$.

Let $m = \lceil n \log_{10} 5 \rceil$ be the smallest integer such that $10^m > 5^n$. For $n > 3$, we have $m < n$.

You want to find $N$ such that $5^N = k 10^m + 5^n$ for some integer $k$. Dividing both sides by $5^n$ yields $$5^{N-n} - 1 = k 2^m/ 5^{n-m}.$$

Thus if you show you can find a large integer $q$ such that $5^q - 1$ is divisible by $2^m$ then you can choose $N$ and $k$ appropriately to conclude the proof.

---

Base case: For $m=2$ we have $5^1 - 1$ divisible by $2^m$. Inductive step: if $5^q-1$ is divisible by $2^m$, then $5^{2q}-1 = (5^q-1)(5^q+1)$ is divisible by $2^{m+1}$.

Answer 2

We will prove that there exists a $N$ such that $5^n$ and $5^N$ have the same last $n$ digits

So what we need to do is to find $5^N\equiv 5^n\pmod{10^n}$

This can be achieved by setting $N=n+\phi (2^n)$

Since $5^N\equiv 5^n\pmod{5^n}$ and $5^N\equiv 5^n\pmod{2^n}$