m and n are positive integers with m < n. The last three decimal digits of 1978m are the same as the last three decimal digits of 1978n. Find m and n such that m + n has the least possible value.
Solution
We require 1978m(1978n-m - 1) to be a multiple of 1000=8·125. So we must have 8 divides 1978m, and hence m ≥ 3, and 125 divides 1978n-m - 1.
By Euler's theorem, 1978φ(125) = 1 (mod 125). φ(125) = 125 - 25 = 100, so 1978100 = 1 (mod 125). Hence the smallest r such that 1978r = 1 (mod 125) must be a divisor of 100 (because if it was not, then the remainder on dividing it into 100 would give a smaller r). That leaves 9 possibilities to check: 1, 2, 4, 5, 10, 20, 25, 50, 100. To reduce the work we quickly find that the smallest s such that 1978s = 1 (mod 5) is 4 and hence r must be a multiple of 4. That leaves 4, 20, 100 to examine.
We find 9782 = 109 (mod 125), and hence 9784 = 6 (mod 125). Hence 97820 = 65 = 36·91 = 26 (mod 125). So the smallest r is 100 and hence the solution to the problem is 3, 103.
Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
12 Oct 1998