Many descendants

Algebra Level pending

Let p p is a prime number. Denote by I ( p ) I(p) the number of irreducible monic polynomials with coefficients in Z / p Z {\mathbb Z/pZ} (integers modulo p p ) that divide the polynomial x p + 1 x + 1. x^{p+1}-x+1.

For p < 100 ? p<100? , what is the largest possible value of I ( p ) I(p) ?

Details and assumptions

A polynomial is monic if its leading coefficient is 1. For example, the polynomial x 3 + 3 x 5 x^3 + 3x - 5 is monic but the polynomial x 4 + 2 x 3 6 -x^4 + 2x^3 - 6 is not.

A polynomial with coefficients in Z / p Z {\mathbb Z/pZ} is irreducible if it cannot be expressed as a product of two non-constant polynomials with coefficients in Z / p Z . {\mathbb Z/pZ}.


The answer is 34.

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.

1 solution

Calvin Lin Staff
May 13, 2014

Denote x p + 1 x + 1 x^{p+1}-x+1 by f p ( x ) , f_p(x), or simply f ( x ) f(x) if p p is assumed fixed. We will consider zeroes of f p f_p in the finite field F p = Z / p Z {\mathbb F}_p={\mathbb Z/pZ} and its finite extensions (alternatively, one can consider the zeroes in the algebraic closure of F p \mathbb F_p ).

First of all, note that 0 0 and 1 1 are never zeroes of f p . f_p. The derivative of f p f_p is x p 1 = ( x 1 ) p x^p-1=(x-1)^p (recall that we are working in characteristic p , p, so ( a + b ) p = a p + b p (a+b)^p=a^p+b^p ). So f f and f f' have no common roots, therefore f f is a product of distinct irreducible monic polynomials with coefficients in F p . \mathbb F_p.

Lemma 1. If p 2 ( m o d 3 ) , p\equiv 2 \pmod 3, then f p ( x ) f_p(x) has no roots in F p . \mathbb F_p. If p 1 ( m o d 3 ) , p\equiv 1 \pmod 3, then f p ( x ) f_p(x) has exactly two roots in F p . \mathbb F_p.

Proof. For a a in F p , \mathbb F_p, we have a p = a a^p =a (in F p \mathbb F_p ). So f p ( a ) = 0 f_p(a)=0 if and only if a 2 a + 1 = 0. a^2-a+1=0. This is equivalent to writing that a 3 + 1 = 0 a^3+1=0 and a 1. a\neq -1. Alternatively, ( a ) 3 = 1 (-a)^3=1 and a 1. -a\neq 1. If p = 3 k + 2 , p=3k+2, then ( a ) 3 = 1 (-a)^3=1 and ( a ) p 1 = 1 (-a)^{p-1}=1 imply a = ( a ) p 1 ( a ) 3 k = 1 , -a=\frac{(-a)^{p-1}}{(-a)^{3k}}=1, hence there are no roots.
One the other hand, if p = 3 k + 1 , p=3k+1, we use the theorem that the multiplicative group of F p \mathbb F_p is cyclic (i.e., there exists a multiplicative generator modulo p p ). So there are exactly two residues modulo p 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 a^2-a+1=0 is 3 -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 ) f_p(x) that is not in F p \mathbb F_p lies in the field of order p 3 . p^3. (That is, it is a root of an irreducible cubic polynomial with coefficients in F p . \mathbb F_p.

Proof. Suppose f p ( a ) = 0. f_p(a)=0. Then a p = a 1 a . a^p=\frac{a-1}{a}. Therefore, a p 2 = ( a 1 a ) p = a p 1 a p = a 1 a 1 ( a 1 a ) = 1 a 1 a^{p^2}=\left(\frac{a-1}{a}\right)^p=\frac{a^p-1}{a^p}=\frac{\frac{a-1}{a}-1}{\left(\frac{a-1}{a}\right)}=\frac{-1}{a-1} Continuing this, a p 3 = ( 1 a ) p = 1 a p = 1 a 1 a 1 = a a^{p^3}=\left(\frac{-1}{a}\right)^p=\frac{-1}{a^p}=\frac{-1}{\frac{a-1}{a} -1}=a The field with p 3 p^3 elements consists of all a a such that a p 3 = a , a^{p^3}=a, so the lemma is proven.

The above two lemmas imply that for p 2 ( m o d 3 ) p\equiv 2 \pmod 3 the polynomial f p f_p is a product of p + 1 3 \frac{p+1}{3} irreducible monic polynomials of degree 3. 3. On the other hand, if p 1 ( m o d 3 ) , p\equiv 1 \pmod 3, then f p f_p is a product of two linear polynomials and p 1 3 \frac{p-1}{3} polynomials of degree 3 3 . It is easy to check that for the primes p < 100 p<100 the largest number of factors is for p = 97 , p=97, which is 2 + 96 3 = 34. 2+\frac{96}{3}=34.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...