## Saturday, January 21, 2006

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

1. 10^2006 mod 252=
100 * 1000^(2004/3) mod 252=
100 * (-8)^(2004/3) mod 252=
25 * (-2)^2006 mod 252=
25 * 4^1003 mod 252

but note that 4^4 = 4 mod 252 so this becomes
25 * 4^3 mod 252=
1600 mod 252=
88 mod 252. ...I think.

2. Oh wait, 4^1003 then reduces to 4, not 4^3. Which means it's 100 mod 252.