Irreducible polynomials

**jamix** · September 15th 2009, 02:25 PM

Is there a formula for quickly calculating the number of irreducible polynomials of degree $n$ over $Z_2$ ?

**NonCommAlg** · September 15th 2009, 05:53 PM

Originally Posted by jamix

Is there a formula for quickly calculating the number of irreducible polynomials of degree $n$ over $Z_2$ ?

yes! here it is: $\frac{1}{n} \sum_{d \mid n} \mu \left(\frac{n}{d} \right)2^d,$ where $\mu$ is the mobius function.

**jamix** · September 15th 2009, 06:30 PM

Ah right, I forgot out that.

I might have a couple more questions about irreducible polynomials, however I think I should be able to solve most of it myself (just wish I hadn't sold my textbook a couple years back

).

**jamix** · September 17th 2009, 01:07 PM

Originally Posted by NonCommAlg

yes! here it is: $\frac{1}{n} \sum_{d \mid n} \mu \left(\frac{n}{d} \right)2^d,$ where $\mu$ is the mobius function.

I used this formula to calculate the number of irreducible polynomials for $n = 5$ . Using it we conclude that there are 6 irreducible polynomials of this degree.

The problem I have though, is that when I tried calculating these irreducibles, I obtained the following 8 polynomials:

$x^5 + x + 1$
$x^5 + x^2 + 1$
$x^5 + x^3 + 1$
$x^5 + x^3 + x^2 + x + 1$
$x^5 + x^4 + 1$
$x^5 + x^4 + x^2 + x + 1$
$x^5 + x^4 + x^3 + x + 1$
$x^5 + x^4 + x^3 + x^2 + 1$

We know that if a degree 5 polynomial is reducible, then it must be divisible by one of $x,x+1,x^2 + x + 1$ , yes? Taking the product of these yields the polynomial $x^4 + x$ over $Z_2$ . Each of the above 8 polynomials $p(x)$ satisfies $gcd(x^4 + x,p(x)) = 1$ , hence all 8 must be irreducible, right?

So whats going on

?

**NonCommAlg** · September 17th 2009, 03:55 PM

Originally Posted by jamix

I used this formula to calculate the number of irreducible polynomials for $n = 5$ . Using it we conclude that there are 6 irreducible polynomials of this degree.

The problem I have though, is that when I tried calculating these irreducibles, I obtained the following 8 polynomials:

$x^5 + x + 1$
$x^5 + x^2 + 1$
$x^5 + x^3 + 1$
$x^5 + x^3 + x^2 + x + 1$
$x^5 + x^4 + 1$
$x^5 + x^4 + x^2 + x + 1$
$x^5 + x^4 + x^3 + x + 1$
$x^5 + x^4 + x^3 + x^2 + 1$

We know that if a degree 5 polynomial is reducible, then it must be divisible by one of $x,x+1,x^2 + x + 1$ , yes? Taking the product of these yields the polynomial $x^4 + x$ over $Z_2$ . Each of the above 8 polynomials $p(x)$ satisfies $gcd(x^4 + x,p(x)) = 1$ , hence all 8 must be irreducible, right?

So whats going on

?

no! two of them are not irreducible: $x^5 + x + 1=(x^2+x+1)(x^3 + x^2 + 1)$ and $x^5 + x^4 + 1 = (x^2+x+1)(x^3+x+1).$

Thread: Irreducible polynomials

LinkBack

Thread Tools

Display

Irreducible polynomials

More problems

Similar Math Help Forum Discussions

Irreducible Polynomials

Irreducible Polynomials f(x) = x^7 - x

Irreducible polynomials

Polynomials written as a product of irreducible polynomials

Irreducible polynomials over Q

Search Tags