7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Oleg567 May 29 '18 at 12:33
  • $\begingroup$ 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)$. $\endgroup$ – poyea May 29 '18 at 12:43
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Easy to check the case $n=1, m=1+100$: last digits of $12^n$ and $12^m$ are: $012$ and $512$. $\endgroup$ – Oleg567 May 29 '18 at 13:05
  • $\begingroup$ 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$... $\endgroup$ – jjhh May 29 '18 at 13:06
  • $\begingroup$ @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$. $\endgroup$ – Oleg567 May 29 '18 at 13:13
  • $\begingroup$ 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 $\endgroup$ – jjhh May 29 '18 at 13:39
  • 1
    $\begingroup$ 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).$$ $\endgroup$ – Oleg567 May 29 '18 at 13:47
2
$\begingroup$

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

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

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:

If $g$ is a primitive root of $p^2$ where $p$ is an odd prime, why is $g$ a primitive root of $p^k$ for any $k \geq 1$?

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

We have

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.