Counting Irreducible Polynomials
Let P n ( x ) = x n + x n − 1 + . . . + x 2 + x + 1 for integral n . How many values of n ∈ [ 1 , 1 0 0 ] are there such that P n ( x ) is irreducible over the rational numbers?
The answer is 26.
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.
3 solutions
I used cyclotomic polynomials. Note that x n + x n − 1 + ⋯ + 1 = x − 1 x n + 1 − 1 = Φ 1 ( x ) d ∣ n + 1 ∏ Φ d ( x ) , where Φ d ( x ) is the d th cyclotomic polynomial. For x − 1 x n + 1 − 1 to be irreducible, the only factor of n + 1 apart from 1 must be n + 1 itself, i.e. n + 1 must be a prime.
I dont get it... is x 4 + x 3 + x 2 + x + 1 reducable polynomial?
Log in to reply
It is irreducible.
The easiest way to see this is what Patrick suggested, namely use the change of variables x = y + 1 , and we get that
x 4 + x 3 + x 2 + x + 1 = y 4 + 5 y 3 + 1 0 y 2 + 1 0 y + 5
Then, we apply Eisenstein's criterion , with p = 5 .
let n=2 then n+1=3 which is a prime but x^3 -1 / x-1 is reducible if my approach to your solution is wrong please tell me
If n=1, Is P 1 ( x ) = x + 1 irreducible over the rational numbers? I think, we'll except n + 1 = 2 , there are 25 values of n, I think.
Log in to reply
Why don't you regard P 1 ( x ) = x + 1 as irreducible?
Last day, I missed some point. :-(
After your comment,
I read 'http://en.wikipedia.org/wiki/Irreducible_polynomial'
Thank you!
I don't get you. x n + x n − 1 + ⋯ + 1 is irreducible over Z [ x ] if and only if n + 1 is prime, and 1 + 1 = 2 is a prime.
if there are a composite number of terms we can group and factorize.
it will be irreducible for prime no of terms.
there are 26 prime numbers from 2 to 101.
When number of terms are prime then we can't group it in equal parts of a number. Eg. If there are 9 terms, we can have 3 groups of 3 each but not possible if number of terms = 7.
There are 25 prime numbers in 1 to 100. 101 is also prime number can 101 terms come if n = 100 is put.
Hence total number of n = 26.
The polynomial is x − 1 x n + 1 − 1 . If n + 1 is prime it is well-known that this polynomial is irreducible (a standard proof is to substitute y = x + 1 and use Eisenstein's criterion on the result). If n + 1 is composite, say divisible by a > 1 , then the polynomial is divisible by x − 1 x a − 1 , hence not irreducible.
There are 2 6 primes between 2 and 1 0 1 , so there are 2 6 possible values of n .