5^an constant mod 100000?

Number Theory Level 4

$\begin{array} { c c c } 25 ^ 1 & \equiv 25 & \pmod{1000} \\ 25 ^ 2 & \equiv 625 & \pmod{1000} \\ 25 ^ 3 & \equiv 625 & \pmod{1000} \\ 25 ^ 4 & \equiv 625 & \pmod{1000} \\ \vdots & \vdots & \vdots \\ \end{array}$

We know that the last 3 digits of $25 ^ n$ will always be a constant 625 for large enough integer values of $n$ .

What is the smallest positive integer value $a$ such that the last 5 digits of $\left( 5 ^ a \right) ^n$ will always be a constant for large enough integer values of $n?$

4 6 8 10

3 solutions

Patrick Corn
Oct 6, 2015

For large enough $n$ , we need that $10^5 | (5^{a(n+1)}-5^{an})$ , or $10^5 | 5^{an}(5^a-1)$ . For large enough $n$ , this happens if and only if $2^5 | (5^a-1)$ . The multiplicative order of $5$ mod $32$ is easily found to be $\fbox{8}$ .

Great work! I was slightly amazed at this result when I was working it out, and then it became "obvious" why it had to be true.

Calvin Lin Staff - 5 years, 8 months ago

I'm hosting a Wiki Collaboration party on Finding the last few digits of a power this Saturday at 8am PDT. Would you be able to contribute?

Calvin Lin Staff - 5 years, 8 months ago

How do we find the multiplicative order of large numbers sir?

Adarsh Kumar - 5 years, 8 months ago

Arjen Vreugdenhil
Nov 30, 2015

I generated the first several powers of 5 and noticed that the first recurrence of the same 5 digits is $5^5 = 03125;\ \ \ \ \ 5^{13} = \dots 03125.$ Since the last five digits determine the last five digits for all subsequent powers of five, the period at which they repeat is $13 - 5 = 8$ . Thus we choose $\boxed{a = 8}$ , and conclude that all $(5^8)^n$ must end in 90625.

It's great that you spotted the pattern. Can you explain in further detail why this pattern exists?

Calvin Lin Staff - 5 years, 6 months ago

There must be a pattern.

Let $L(n)$ be the last five digits of $5^n$ . Then $L(n+1)$ is uniquely determined by $L(n)$ , so that (by simple induction) $\text{if}\ L(n+a) = L(n)\ \ \ \text{then}\ \ \ \ L(n+ka+m) = L(n+m)\ \ (k, m = 0, 1, \dots).$ In other words, the $a$ numbers $L(n)$ through $L(n+a-1)$ repeat infinitely.

Now suppose that there were no repeating pattern. Then all $L(n)$ must be different, because as soon as there is a repeat there is an infinite pattern. However, for the last five digits there are only $10^5$ possibilities. Therefore the $L(n)$ cannot be all different; there must be repetition at some point; and therefore an infinitely repeating pattern.

Following this argument, it may take up to $10^5$ steps to enter the repeating pattern; even if we account for the fact that all higher powers of 5 end in 125 and 625, there are still 200 possibilities to try. In a sense I was therefore lucky to spot the pattern so soon!

Arjen Vreugdenhil - 5 years, 6 months ago

Great, that's the existence proof for the pattern, which is the typical periodic in a linear recurrence argument.

Can you give the construction proof? What is so special about 8, in particular $A = 5^8 - 1$ , such that $A \times 5^n \equiv 5^n \pmod{10^5 }$ ?

Calvin Lin Staff - 5 years, 6 months ago

Rushikesh Jogdand
Mar 12, 2016

@Calvin Lin There is slight error in problem. $25 \equiv 25 \pmod{100}$ should be $25 \equiv 25 \pmod{1000}$ , and so since it says last $3$ digits.

Thanks. I've edited the problem accordingly.

In future, if you spot any errors with a problem, you can “report” it by selecting "report problem" in the menu. This will notify the problem creator who can fix the issues.

Calvin Lin Staff - 5 years, 3 months ago

Thanks.

I ignored the "report problem" option.

Rushikesh Jogdand - 5 years, 3 months ago

5^an constant mod 100000?

3 solutions

0 pending reports