IMO 1978 Problem A1 m and n are positive integers with m < n. The last three decimal digits of 1978 m are the same as the last three decimal digits of 1978 n . Find m and n such that m + n has the least possible value.
We require 1978 m (1978 n-m - 1) to be a multiple of 1000=8·125. So we must have 8 divides 1978 m , and hence m ≥ 3, and 125 divides 1978 n-m - 1. By Euler's theorem, 1978 φ(125) = 1 (mod 125). φ(125) = 125 - 25 = 100, so 1978 100 = 1 (mod 125). Hence the smallest r such that 1978 r = 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 1978 s = 1 (mod 5) is 4 and hence r must be a multiple of 4. That leaves 4, 20, 100 to examine. We find 978 2 = 109 (mod 125), and hence 978 4 = 6 (mod 125). Hence 978 20 = 6 5 = 36·91 = 26 (mod 125). So the smallest r is 100 and hence the solution to the problem is 3, 103. s 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. 20th IMO 1978 © John Scholes jscholes@kalva.demon.co.uk 12 Oct 1998