52nd Putnam 1991 Problem B5 p a prime > 2. How many residues mod p are both squares and squares plus one? [For example, for p = 7, there are two such residues: 1 = 1 2 = 0 2 + 1 and 2 = 3 2 = 1 2 + 1.] Solution
: [p/4] + 1. Straightforward (although I made a mess of it first time around). We require (x + y)(x - y) = 1 (mod p). But this is just the statement that (x - y) is the inverse of (x + y). Any non-zero residue has a unique inverse mod p. So we may take k to be any of the p - 1 values 1, 2, ... , p - 1 and then (x + y) = k, (x - y) = 1/k (mod p). Thus there are p - 1 solutions pairs (x, y): ( (k + 1/k)/2, (k - 1/k)/2 ) k = 1, 2, ... , p - 1. We are not quite there yet, because we require the number of distinct h such that h = x 2 = y 2 + 1 (mod p), and some of the solution pairs for (x, y) give the same value h. In fact, z 2 = s (mod p) has either two or zero solutions unless s = 0, when it has just 1. Hence there are in general 4 solution pairs (±x 0 , ±y 0 ) corresponding to a given value of h. But there are always just two, namely (±1, 0), corresponding to h = 1. If -1 is a quadratic residue of p, then there are two solutions (0, ±y 0 ) corresponding to h = 0, otherwise none. But we show below that -1 is a quadratic residue iff p = 1 (mod 4). Hence if p = 1 (mod 4), then there are (p - 1 - 4)/4 + 2 = (p + 3)/4 = [p/4] + 1 solutions. Similarly, if p = 3 (mod 4), then there are (p - 1 - 2)/4 + 1 = (p + 1)/4 = [p/4] + 1 solutions. It remains to show when -1 is a quadratic residue, although this could probably be assumed in the exam. In any case, it is pure bookwork. If p = 3 (mod 4) and -1 is a quadratic residue, then we would have t 2 = -1 (mod p) and hence t p-1 = (-1) (p-1)/2 = -1 (mod p). But t p-1 = 1 (mod p) [Fermat's theorem, proof: both t, 2t, 3t, ... , (p-1)t and 1, 2, 3, ... , p - 1 are complete sets of non-zero residues, so (p-1)! t p-1 = (p-1)! (mod p) and hence t p-1 = 1 (mod p)], and p does not divide 2. Contradiction. Conversely, if p = 1 (mod 4), then we show that (1·2·3. ... . (p-1)/2) 2 = -1 (mod p). But the square is just (p - 1)! so we have to prove Wilson's theorem. s is its own inverse mod p iff s = 1 or p - 1. So the other p - 3 residues divide into pairs with product 1 and hence (p - 1)! = p - 1 = - 1 (mod p). 52nd Putnam 1991 © John Scholes jscholes@kalva.demon.co.uk 24 Sep 1999