19th CanMO 1987 Problem 1 Find all positive integer solutions to n! = a 2 + b 2 for n < 14. Solution
: 2! = 1 2 + 1 2 , 6! = 24 2 + 12 2 . A necessary condition for N to be the sum of two squares is that N does not have a prime p = 3 mod 4 such that the highest power of p dividing N is odd. Thus for n = 3, 4, 5 the highest power of 3 dividing n! is 3 1 . For n = 7, 8, 9, 10, 11, 12, 13 the highest power of 7 dividing n! is 7 1 . So in all those cases n! cannot be written as a sum of two squares. Obviously 1! cannot (because the smallest sum of two squares is 2) and we have exhibited 2! and 6! as a sum of two squares. To prove the criterion, note that if p divides N and N = a 2 + b 2 then a 2 = -b 2 mod p, so if a and b are not multiples of p, then we can take c such that ac = 1 and get x 2 = -1 mod p, where x = bc. But if p = 3 mod 4, then (p-1)/2 is odd, so x p-1 = (-1) odd = -1 mod p, whereas we know that x p-1 = 1 mod p for all x not zero mod p. 19th CanMO 1987 © John Scholes jscholes@kalva.demon.co.uk 21 June 2002