### 48th Putnam 1987

Problem B6

F is a finite field with p2 elements, where p is an odd prime. S is a set of (p2 - 1)/2 distinct non-zero elements of F such that for each a ∈ F, just one of a and -a is in S. Prove that the number of elements in S ∩ {2a: a ∈ S} is even.

Solution

Put q=(p2-1)/2, so S has q elements. Since p is odd, q is even. For each b there is just one c such that b = 2c. Just one of c, -c is in S. So for each b in S we can find a unique f(b) in S such that b = 2f(b)k(b) where k(b) = ±1. We cannot have f(a) = f(b) unless a = b, so as b runs through the elements of S, so does f(b). Hence ∏ a = 2qk ∏ a, where the product is taken over all elements of S and k is the number of negative k(a). So k = 2q (mod p). k(a) is positive iff a belongs to the required intersection. The number of elements in S is even, so the number of positive k(a) is even iff the number of negative k(a) is even. Hence we wish to show that k = 1. But q = (p-1) x (p+1)/2. We know that 2p-1 = 1 (mod p), so 2q = 1 (mod p) as required.