F is a finite field with n elements. n is odd. x2 + bx + c is an irreducible polynomial over F. For how many elements d ∈ F is x2 + bx + c + d irreducible?
Since n is odd, h ≠ -h for any h ∈ F. So there are exactly (n + 1)/2 quadratic residues. Since n is odd, we may write b as 2k, and so we are interested in d for which (x + k)2 = k2 - c - d is irreducible. In other words, d for which k2 - c - d is a quadratic non-residue. But k2 - c - d runs through all the elements of F, so there are just (n - 1)/2 values of d which give a quadratic non-residue.
40th Putnam 1979
© John Scholes
4 Dec 1999