Results 1 to 5 of 5

Math Help - Irreducible polynomials

  1. #1
    Member
    Joined
    Jun 2008
    Posts
    148

    Irreducible polynomials

    Is there a formula for quickly calculating the number of irreducible polynomials of degree n over Z_2?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by jamix View Post

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2008
    Posts
    148
    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 ).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Jun 2008
    Posts
    148

    More problems

    Quote Originally Posted by NonCommAlg View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by jamix View Post
    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).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Irreducible Polynomials
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 18th 2011, 01:11 AM
  2. Irreducible Polynomials f(x) = x^7 - x
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: July 24th 2011, 10:47 PM
  3. Irreducible polynomials
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 23rd 2011, 01:07 PM
  4. Replies: 7
    Last Post: January 8th 2010, 03:13 AM
  5. Irreducible polynomials over Q
    Posted in the Advanced Algebra Forum
    Replies: 7
    Last Post: May 23rd 2009, 10:18 PM

Search Tags


/mathhelpforum @mathhelpforum