It Only Matters In The End. Topic: Number Theory. Level: Olympiad.

Problem: (1978 IMO - #1) We consider all the pairs $(m,n)$ of integer numbers, so that $n>m \geq 1$ and so that their last three digits from the decimal writing of $1978^{m}$ are the same with those three last digits from the decimal writing of $1978^{n}$. Find all the pairs $(m,n)$ with these properties so that the sum $m+n$ is minimum.

Solution: Basically it's asking us to find the smallest $m$ and $n$ such that $ 1978^m \equiv 1978^n \pmod{1000} $ or $ 1978^n-1978^m \equiv 0 \pmod{1000} $. By the looks of this problem, Euler's Totient Theorem might come in handy again. But we have a small problem - $ (1978,1000) \neq 1 $.

So we try dividing out all the factors of $ 2 $ in $ 1000 $.

By the Totient Theorem, we find $ 1978^{\phi(125)} = 1978^{100} \equiv 1 \pmod{125} $ and that $100$ is also the smallest power for which this is true. This means $ 1978^{100} = 125k+1 $ for some positive integer $k$.

Hence $m$ and $n$ differ by at least $100$. Suppose $ n = m+100 $.

Then $ 1978^{m+100}-1978^m = 1978^m(1978^{100}-1) \equiv \pmod{1000} $. Since the second part is odd, all the powers of two, there must be at least three of them, come from $ 1978^m $. Hence $ m \ge 3 $. But since we know $ 1978^{100}-1 \equiv 0 \pmod{125} $, we have $ 1978^m(1978^{100}-1) $ divisible by both $ 8 $ and $ 125 $, which means it's divisible by $ 1000 $, so $ m = 3 $ is the smallest possible value that works, giving $ n = 103 $.

Therefore, our smallest $ m+ n = 106 $. QED.

--------------------

Comment: Kind of a strange problem, with the minimum value, reminiscent of many AIME problems. Ultimately, not too difficult, though.

--------------------

Practice Problem: Find the value of $ 10^{2006} \pmod{252} $.