# If the last 3 digits of $2012^m$ and $2012^n$ are identical, find the smallest possible value of $m+n$.

Let $m$ and $n$ be positive integers such that $m>n$. If the last 3 digits of $2012^m$ and $2012^n$ are identical, find the smallest possible value of $m+n$.

Since the 100's digit is 0 in both cases, I just did $2012^m \equiv 2012^n \mod 1000$, and got $12^m \equiv 12^n\mod 1000$ but I'm not sure where to go from there. Trying to compute the first few powers of $12$ will only get the numbers larger and the pattern doesn't seem to emerge that soon.

• You can reduce result to last $3$ digits each step: for example, $12^{10}\equiv 224 (\bmod 1000)$; then $12^{11} \equiv 12\cdot 224 \equiv 668 (\bmod 1000)$, $12^{12} \equiv 12\cdot 668 \equiv 256 (\bmod 1000)$ etc. – Oleg567 May 29 '18 at 12:33
• If $m,n$ fulfill $12^m \equiv 12^n\mod 1000$, $1000\mid (12^{m}-12^n)$ and $1000\mid 12^{n}(12^{m-n}-1)$. – poyea May 29 '18 at 12:43

Let find periodicity of last digit: $$1\underline{2}, 14\underline{4}, 172\underline{8}, 2073\underline{6}, 24883\underline{2}, ...$$ Since $12^1 \equiv 12^5 \equiv 2 \bmod(10)$, we conclude that $12^k\equiv 12^{k+4} (\bmod 10)$.

Now find periodicity of last $2$ digits, using this $4$-periodicity of last digit: since $12^4 \equiv 36 (\bmod 100)$,

$12^1 =12 (\bmod 100)$,
$12^5 \equiv 12 \cdot 12^4 \equiv 12\cdot 36 \equiv 32 (\bmod 100)$,
$12^9 \equiv 12^5 \cdot 12^4 \equiv 32\cdot 36 \equiv 52 (\bmod 100)$,
$12^{13} \equiv 12^9 \cdot 12^4 \equiv 52\cdot 36 \equiv 72 (\bmod 100)$,
$12^{17} \equiv 12^{13}\cdot 12^4 \equiv 72\cdot 36 \equiv 92 (\bmod 100)$,
$12^{21} \equiv 92\cdot 36 \equiv 12 (\bmod 100)$;

so, periodicity of last $2$ digits is $20$.

Finally, find periodicity of last $3$ digits: since $12^{20} \equiv 176 (\bmod 1000)$, we have:

$12^2 \equiv 144 (\bmod 1000)$;
$12^{22} \equiv 144 \cdot 176 \equiv 344 (\bmod 1000)$;
$12^{42} \equiv 344 \cdot 176 \equiv 544 (\bmod 1000)$;
$12^{62} \equiv 544 \cdot 176 \equiv 744 (\bmod 1000)$;
$12^{82} \equiv 744 \cdot 176 \equiv 944 (\bmod 1000)$;
$12^{102} \equiv 944 \cdot 176 \equiv 144 (\bmod 1000)$;

So, $$12^2 = 144,$$ $$12^{102} \equiv 144 (\bmod 1000).$$

$$(m+n = 104)$$

• Easy to check the case $n=1, m=1+100$: last digits of $12^n$ and $12^m$ are: $012$ and $512$. – Oleg567 May 29 '18 at 13:05
• I like your solution, but maybe this should be obvious but I don't understand how since $12^4≡36(mod100)$ leads to 4-periodicity (And similarly for $12^20$... – jjhh May 29 '18 at 13:06
• @Helena: Once we noticed that $12^5 \equiv 12^1 (\bmod 10)$, we can claim that $12^{k+4} \equiv 12^k (\bmod 10)$, therefore to have $2$-digital periodicity, we should check powers with step $4$. This $12^4 \equiv 36 (\bmod 100)$ is for fast "jumping" over powers with step $4$. – Oleg567 May 29 '18 at 13:13
• Oh okay. For computing $12^5$ that seems manageable by hand, but getting the last three digits of $12^{20}$ seems a bit troublesome still – jjhh May 29 '18 at 13:39
• To compute last $3$ digits of $12^{20}$, we can do following: $12^5 = 248832$, so $$12^5\equiv 832 (\bmod 1000),$$ then $$12^{10} = (12^5)^2 \equiv 832^2 \equiv 224 (\bmod 1000),$$ and finally $$12^{20 } = (12^{10})^2 \equiv 224^2 \equiv 176 (\bmod 1000).$$ – Oleg567 May 29 '18 at 13:47

You have $12^m\equiv 12^n\pmod{10^3}$ hence $12^m\equiv 12^n\pmod{2^3}$ and $12^m\equiv 12^n\pmod{5^3}$.

For the latter, we have $12^{m-n}\equiv 1\pmod{5^3}$, hence $m\equiv n\pmod{100}$ because the multiplicative order of $12$ modulo $5^3$ is $100$, as computed here.

On the other hand, $12^n(12^{m-n}-1)\equiv 0\pmod{2^3}$ from which $12^n\equiv 0\pmod{2^3}$ which holds for $n\geq 2$.

Thus $n=2$ and $m=102$ is the smallest solution with sum $m+n=104$.

• Actually, $2$ is a primitive root mod $5^n$ for all $n$, and so has order $4\cdot 5^{n-1}$. – lhf May 29 '18 at 13:16

As $12^{m-n}-1$ is odd, $2^3$ must divide $12^n\implies n\ge2$

As $(12^n,5)=1,5^3$ must divide $12^{m-n}-1$

$\iff12^{m-n}\equiv1\pmod{125}$

As $12^2\not\equiv1\pmod5\implies$ord$_512=4$

Now $12^4=(145-1)^2\not\equiv1\pmod{25}\implies$ord$_{25}12=4\cdot5$

So, $12$ is a primitive root $\pmod{5^r},r\ge1$

$\implies m-n$ must be divisible by $\phi(125)$

Reference:

Here Order of numbers modulo $p^2$ I've proved if ord$_pa=d,$ord$_{p^2}a=d$ or $pd$

The last 3 digits repeat periodically, we have to find the period. First of all, let me please write the code to have a certain answer, the human solution follows:

Sage code:

L = []
R = Zmod(1000)
b = R(2012)
a = b
n = 1    # corresponds to a = b^1
while a not in L:
L.append(a)
print "2012^%3s = %3s modulo 1000" % ( n, a )
n += 1
a *= R(2012)
print "n = %s :: Value repeated = %s" % ( n, a )


Results (omissions in the middle...)

2012^  1 =  12 modulo 1000
2012^  2 = 144 modulo 1000
2012^  3 = 728 modulo 1000
2012^  4 = 736 modulo 1000
2012^  5 = 832 modulo 1000
2012^  6 = 984 modulo 1000
2012^  7 = 808 modulo 1000
2012^  8 = 696 modulo 1000
2012^  9 = 352 modulo 1000
2012^ 10 = 224 modulo 1000
2012^ 11 = 688 modulo 1000

::::::::::::::::::::::::::

2012^ 95 = 968 modulo 1000
2012^ 96 = 616 modulo 1000
2012^ 97 = 392 modulo 1000
2012^ 98 = 704 modulo 1000
2012^ 99 = 448 modulo 1000
2012^100 = 376 modulo 1000
2012^101 = 512 modulo 1000
n = 102 :: Value repeated = 144


Now the human solution.

We want $2012^m = 2012^n$ modulo $1000$ with minimal values for $m>n>0$. The equality modulo $1000$ is equivalent to the following two equalities: \begin{aligned} 2012^m &= 2012^n\text { modulo }2^3 = 8\ ,\qquad\text{ and }\\ 2012^m &= 2012^n\text { modulo }5^3 = 125\ . \end{aligned} For $n=1$ we have $2012^n=2012=4$ modulo $8$. For $n>1$ we have of course $2012^n=4^n=0$ modulo $8$. So the first time we can have a repetition is for $n=2$. The repetition occurs - looking now on the side with rests modulo $125$, latest after $$\phi(125)=\phi(5^3)=\frac 45\cdot 5^3=100$$ steps. (Since $2012$ is prime to $125$, here $\phi$ is the Euler indicator function.)

From the above computation we know that $100$ is the minimal period. To show this, it is enough to see that

• $2012^{100/2}$, and

• $2012^{100/5}$,

is not one modulo $125$. One can compute for instance

sage: 2012^10 % 125
99
sage: 2012^20 % 125, 99^2 % 125
(51, 51)
sage: 2012^50 % 125, 99^5 % 125
(124, 124)


So the order of $2012=12$ in the multiplicative group $(\Bbb Z/125)^\times$ of order $\phi(125)=100$ is indeed $100$, the full possible order, since no immediate divisors are. We can also ask

sage: R = Zmod(125)
sage: R(2012).multiplicative_order()
100


So the minimal values are $m=102 >n=2>0$.

We have

$$12^n \equiv 12^{n+100}\Rightarrow n=2,m=102\to n+m=104$$

• Wait how do I know that $12^n \equiv 12^{n+100}$? – jjhh May 29 '18 at 13:08