### 35th Putnam 1974

Problem A3

Which odd primes p can be written in the form m2 + 16n2? In the form 4m2 + 4mn + 5n2 ,where m and n may be negative? [You may assume that p can be written in the form m2 + n2 iff p = 1 (mod 4).]

Solution

Answer: p = 1 (mod 8); p = 5 (mod 8).

(A) m2 + 16n2.

We show first that m2 + 16n2 = 1 (mod 8). Clearly m is odd, otherwise m2 + 16n2 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 m2 + 16n2 = 1 (mod 8).

Conversely, suppose p = 1 (mod 8). Take, p = M2 + N2. Without loss of generality, M is odd and N even. Hence N2 = 0 (mod 8), so N is a multiple of 4.

(B) 4m2 + 4mn + 5n2.

n must be odd (otherwise p would be even). But 4m2 + 4mn + 5n2 = (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 = M2 + N2 = 5 (mod 8), then wlog M is odd and N even. Take N = 2n. Since M2 = 1 (mod 8), N2 = 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 M2 = 4m2 + 4mn + n2 and p = 4m2 + 4mn + 5n2, as required.