Let is a prime number. Denote by the number of irreducible monic polynomials with coefficients in (integers modulo ) that divide the polynomial
For , what is the largest possible value of ?
Details and assumptions
A polynomial is monic if its leading coefficient is 1. For example, the polynomial is monic but the polynomial is not.
A polynomial with coefficients in is irreducible if it cannot be expressed as a product of two non-constant polynomials with coefficients in
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Denote x p + 1 − x + 1 by f p ( x ) , or simply f ( x ) if p is assumed fixed. We will consider zeroes of f p in the finite field F p = Z / p Z and its finite extensions (alternatively, one can consider the zeroes in the algebraic closure of F p ).
First of all, note that 0 and 1 are never zeroes of f p . The derivative of f p is x p − 1 = ( x − 1 ) p (recall that we are working in characteristic p , so ( a + b ) p = a p + b p ). So f and f ′ have no common roots, therefore f is a product of distinct irreducible monic polynomials with coefficients in F p .
Lemma 1. If p ≡ 2 ( m o d 3 ) , then f p ( x ) has no roots in F p . If p ≡ 1 ( m o d 3 ) , then f p ( x ) has exactly two roots in F p .
Proof. For a in F p , we have a p = a (in F p ). So f p ( a ) = 0 if and only if a 2 − a + 1 = 0 . This is equivalent to writing that a 3 + 1 = 0 and a = − 1 . Alternatively, ( − a ) 3 = 1 and − a = 1 . If p = 3 k + 2 , then ( − a ) 3 = 1 and ( − a ) p − 1 = 1 imply − a = ( − a ) 3 k ( − a ) p − 1 = 1 , hence there are no roots.
One the other hand, if p = 3 k + 1 , we use the theorem that the multiplicative group of F p is cyclic (i.e., there exists a multiplicative generator modulo p ). So there are exactly two residues modulo p that satisfy the above condition. (Note: alternatively, one can use the quadratic reciprocity law: the discriminant of the equation a 2 − a + 1 = 0 is − 3 and the equation has two or zero solutions depending on whether or not it is a quadratic residue).
Lemma 2. Every root of f p ( x ) that is not in F p lies in the field of order p 3 . (That is, it is a root of an irreducible cubic polynomial with coefficients in F p .
Proof. Suppose f p ( a ) = 0 . Then a p = a a − 1 . Therefore, a p 2 = ( a a − 1 ) p = a p a p − 1 = ( a a − 1 ) a a − 1 − 1 = a − 1 − 1 Continuing this, a p 3 = ( a − 1 ) p = a p − 1 = a a − 1 − 1 − 1 = a The field with p 3 elements consists of all a such that a p 3 = a , so the lemma is proven.
The above two lemmas imply that for p ≡ 2 ( m o d 3 ) the polynomial f p is a product of 3 p + 1 irreducible monic polynomials of degree 3 . On the other hand, if p ≡ 1 ( m o d 3 ) , then f p is a product of two linear polynomials and 3 p − 1 polynomials of degree 3 . It is easy to check that for the primes p < 1 0 0 the largest number of factors is for p = 9 7 , which is 2 + 3 9 6 = 3 4 .