35th Putnam 1974 Problem A3 Which odd primes p can be written in the form m 2 + 16n 2 ? In the form 4m 2 + 4mn + 5n 2 ,where m and n may be negative? [You may assume that p can be written in the form m 2 + n 2 iff p = 1 (mod 4).] Solution
: p = 1 (mod 8); p = 5 (mod 8). (A) m 2 + 16n 2 . We show first that m 2 + 16n 2 = 1 (mod 8). Clearly m is odd, otherwise m 2 + 16n 2 would be even. But odd squares are = 1 (mod 8) (because (2N+1) 2 = 4N(N+1) + 1 and N(N+1) is even). Hence m 2 + 16n 2 = 1 (mod 8). Conversely, suppose p = 1 (mod 8). Take, p = M 2 + N 2 . Without loss of generality, M is odd and N even. Hence N 2 = 0 (mod 8), so N is a multiple of 4. (B) 4m 2 + 4mn + 5n 2 . n must be odd (otherwise p would be even). But 4m 2 + 4mn + 5n 2 = (2m + n) 2 + (2n) 2 . The first term is congruent to 1 and the second to 4 mod 8. Hence p = 5 (mod 8). Conversely, if p = M 2 + N 2 = 5 (mod 8), then wlog M is odd and N even. Take N = 2n. Since M 2 = 1 (mod 8), N 2 = 4 (mod 8) and hence n is odd. So M + n is even and we may set m = (M - n)/2. Now M = 2m + n, so M 2 = 4m 2 + 4mn + n 2 and p = 4m 2 + 4mn + 5n 2 , as required. 35th Putnam 1974 © John Scholes jscholes@kalva.demon.co.uk 18 Aug 2001