IMO 1978 · Problem 1

\(m\) and \(n\) are natural numbers with \(1 \le m < n\). In their decimal representations, the last three digits of \(1978^m\) are equal, respectively, to the last three digits of \(1978^n\). Find \(m\) and \(n\) such that \(m+n\) has its least value.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{m=3,\qquad n=103,\qquad \min(m+n)=106.} \]

Solution

Put \(d=n-m>0\). The last three digits agree exactly when \[ 1000\mid 1978^n-1978^m =1978^m(1978^d-1). \] Since \(1000=8\cdot125\) and \(8,125\) are relatively prime, we consider these two factors separately.

As \(1978=2\cdot989\) and \(1978^d-1\) is odd, the difference contains exactly \(m\) factors of \(2\). Thus it is divisible by \(8\) exactly when \[ m\ge3. \] Also, \(1978\) is relatively prime to \(125\), so divisibility by \(125\) is equivalent to \[ 1978^d\equiv1\pmod{125}. \] We prove that this holds exactly when \(100\mid d\).

First, reduction modulo \(5\) gives \(3^d\equiv1\pmod5\). The successive powers of \(3\) modulo \(5\) repeat as \(3,4,2,1\), so \(4\mid d\). Write \(d=4k\). Calculating modulo \(125\), \[ 1978\equiv103,\qquad 1978^2\equiv109,\qquad 1978^4\equiv6. \] Consequently, \(6^k\equiv1\pmod{125}\). By the binomial theorem, \[ 6^k=(1+5)^k\equiv1+5k\pmod{25}. \] Hence \(5\mid k\), so write \(k=5t\). Since \[ 6^5=7776\equiv26\pmod{125}, \] we obtain \[ 1\equiv6^{5t}\equiv26^t =(1+25)^t\equiv1+25t\pmod{125}. \] Therefore \(5\mid t\), proving \(100\mid d\).

Conversely, the same calculations give \[ 1978^{100}\equiv6^{25}\equiv26^5 =(1+25)^5\equiv1\pmod{125}, \] so every positive multiple of \(100\) satisfies the required congruence.

Thus the original condition holds exactly when \(m\ge3\) and \(n-m\) is a positive multiple of \(100\). Therefore \[ m+n=2m+(n-m)\ge2\cdot3+100=106. \] Equality is attained precisely at \(m=3\) and \(n=103\), as claimed.

The solution was checked against John Scholes' IMO solution archive (Kalva).