# Thread: Irreducible polynomials

1. ## Irreducible polynomials

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

2. Originally Posted by jamix

Is there a formula for quickly calculating the number of irreducible polynomials of degree $\displaystyle n$ over $\displaystyle Z_2$?
yes! here it is: $\displaystyle \frac{1}{n} \sum_{d \mid n} \mu \left(\frac{n}{d} \right)2^d,$ where $\displaystyle \mu$ is the mobius function.

3. 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 ).

4. ## More problems

Originally Posted by NonCommAlg
yes! here it is: $\displaystyle \frac{1}{n} \sum_{d \mid n} \mu \left(\frac{n}{d} \right)2^d,$ where $\displaystyle \mu$ is the mobius function.
I used this formula to calculate the number of irreducible polynomials for $\displaystyle 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:

$\displaystyle x^5 + x + 1$
$\displaystyle x^5 + x^2 + 1$
$\displaystyle x^5 + x^3 + 1$
$\displaystyle x^5 + x^3 + x^2 + x + 1$
$\displaystyle x^5 + x^4 + 1$
$\displaystyle x^5 + x^4 + x^2 + x + 1$
$\displaystyle x^5 + x^4 + x^3 + x + 1$
$\displaystyle 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 $\displaystyle x,x+1,x^2 + x + 1$, yes? Taking the product of these yields the polynomial $\displaystyle x^4 + x$ over $\displaystyle Z_2$. Each of the above 8 polynomials $\displaystyle p(x)$ satisfies $\displaystyle gcd(x^4 + x,p(x)) = 1$, hence all 8 must be irreducible, right?

So whats going on ?

5. Originally Posted by jamix
I used this formula to calculate the number of irreducible polynomials for $\displaystyle 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:

$\displaystyle x^5 + x + 1$
$\displaystyle x^5 + x^2 + 1$
$\displaystyle x^5 + x^3 + 1$
$\displaystyle x^5 + x^3 + x^2 + x + 1$
$\displaystyle x^5 + x^4 + 1$
$\displaystyle x^5 + x^4 + x^2 + x + 1$
$\displaystyle x^5 + x^4 + x^3 + x + 1$
$\displaystyle 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 $\displaystyle x,x+1,x^2 + x + 1$, yes? Taking the product of these yields the polynomial $\displaystyle x^4 + x$ over $\displaystyle Z_2$. Each of the above 8 polynomials $\displaystyle p(x)$ satisfies $\displaystyle 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: $\displaystyle x^5 + x + 1=(x^2+x+1)(x^3 + x^2 + 1)$ and $\displaystyle x^5 + x^4 + 1 = (x^2+x+1)(x^3+x+1).$