6th APMO 1994 Problem 3 Find all positive integers n such that n = a 2 + b 2 , where a and b are relatively prime positive integers, and every prime not exceeding √n divides ab. Solution
: 2 = 1 2 + 1 2 , 5 = 1 2 + 2 2 , 13 = 2 2 + 3 2 . The key is to use the fact that a and b are relatively prime. We show in fact that they must differ by 1 (or 0). Suppose first that a = b. Then since they are relatively prime they must both be 1. That gives the first answer above. So we may take a > b. Then (a - b) 2 < a 2 + b 2 = n, so if a - b is not 1, it must have a prime factor which divides ab. But then it must divide a or b and hence both. Contradiction. So a = b + 1. Now (b - 1) 2 < b 2 < n, so any prime factor p of b - 1 must divide ab = b(b + 1). It cannot divide b (or it would divide b and b - 1 and hence 1), so it must divide b + 1 and hence must be 2. But if 4 divides b - 1, then 4 does not divide b(b - 1), so b - 1 must be 0, 1 or 2. But it is now easy to check the cases a, b = (4, 3), (3, 2), (2, 1). 6th APMO 1994 © John Scholes jscholes@kalva.demon.co.uk 11 Apr 2002