Find all positive integers n such that n = a2 + b2, where a and b are relatively prime positive integers, and every prime not exceeding √n divides ab.
Solution
Answer: 2 = 12 + 12, 5 = 12 + 22, 13 = 22 + 32.
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 < a2 + b2 = 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 < b2 < 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).
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002