Consider polynomials in one variable over the finite field F2 with 2 elements. Show that if n + 1 is not prime, then 1 + x + x2 + ... + xn is reducible. Can it be reducible if n + 1 is prime?
Let n+1 = ab, then 1 + x + x2 + ... + xn = (1 + x + x2 + ... + xa-1)(1 + xa + x2a + ... + xab-a). Note that this does not depend upon the field having two elements.
Yes. For example, (1 + x + x3)(1 + x2 + x3) = 1 + x + x2 + x3 + x4 + x5 + x6.
22nd Putnam 1961
© John Scholes
15 Feb 2002