Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Show reducibility

  1. May 25, 2005 #1
    Hi!

    I need to show that x^4+1 is reducible modulo p for all prime p.

    I was thinking to show that it has to have a root in some odd extension of Zp, which would force that root to be in Zp. Am I on the right track?
     
  2. jcsd
  3. May 25, 2005 #2
    A quick maple experiment seems to show that x^4+1 rarely has a root mod p where p is prime. You can probably show it factors into two quadratics.
     
  4. May 26, 2005 #3
    No squares are reducible modulo p where p==3 Mod 4.

    Take [tex]X^4+1 \equiv 0 Mod 3[/tex]
     
    Last edited: May 26, 2005
  5. May 26, 2005 #4
    This problem seems to be equivilant to saying that either -1 has a squareroot or 4 has a 4th root mod p. I seem to recall that -1 has a squareroot iff p is congruent to 1 mod 4. Can it be shown (easily) that if p prime is congruent to 3 mod 4 that 4 has a fourth root mod p?

    Steven
     
  6. May 28, 2005 #5
    Did you ever figure out how to show that [tex]X^4+1[/tex] factors mod p for any prime p? I finally figured out one way to show it but it is long and complicated. I would love to see a simple way. I will share the complicated way if anyone is really interested.

    Steven
     
  7. May 28, 2005 #6
    That would be interesting.
     
  8. May 28, 2005 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, it's already been suggested to try factoring into two quadratics. The obvious "simple" thing to try is:

    x^4 + 1 = (x^2 + a) (x^2 + b) = x^4 + (a + b) x^2 + ab

    So all you need to do is solve the system:

    a+b = 0
    ab = 1

    modulo p. Can you do that? Guess only if -1 has a square root.


    So, try the generic case:

    (x^2 + ax + b) (x^2 + cx + d) = x^4 + (a + c) x^3 + (b + d + ac) x^2 + (ad + bc) x + bd

    So,

    a + c = 0
    b + d + ac = 0
    ad + bc = 0
    bd = 1

    If a is not zero, solving this comes down to whether one of m and -m have a square root mod p (For a particular m). That is guaranteed to be true if, *drumroll*, -1 does not have a square root!
     
  9. May 28, 2005 #8
    Well yeah... the m you're looking for in this case is m=2. And if [tex]p\equiv 3 (mod\,4)[/tex] then either 2 or -2 has a square root (in fact for every m, either [tex]\pm m[/tex] has a square root). And if [tex] p\equiv 1(mod\, 4)[/tex] then -1 has a square root. But showing this is basically the same as proving Wilson's theorem (well not quite) and isn't that trivial. I was hoping there would be something simpler like some trick that shows that [tex]\mathbb{Z}_p[x]/<x^4+1>[/tex] can't be a field.
     
  10. May 28, 2005 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The proof doesn't actually care when -1 has a square root mod p -- just that one method works when it does, and the other when it does not.

    In any case, Wilson's theorem has been proven, so it's fair game to use. :smile: (And I'm using Quadratic Recipricosity! heaven forbid!)


    Well, I have a proof that Zp[x] / <x4 + 1> can't be a field... it starts off by assuming x4 + 1 factors as (x2 + a) (x2 + b) (modulo p) ... :biggrin:
     
  11. May 29, 2005 #10
    I'm clearly a little dense today (and I should clearly be trying to sleep and not reading physicsforums) but why is it clear that either -1 has a square root or [tex]\pm m[/tex] has a square root for each prime. I'm sure it's something simple that I'm missing but I'm just not seeing it.

    Steven
     
  12. May 29, 2005 #11
    If -1 is present as a quadratic residue, then so is -A, since there is an X present such that [tex]X^2*A \equiv -A \equiv -u^2 \equiv (Xu)^2 Mod p[/tex]

    In the other case, if both A and -A are present as quadratic residues, then (X/Y)^2 == A/-A ==-1 Mod p.

    Wilson's Theorem (Wilson became a lawyer and never proved his theorem so I have been told) is not hard to prove if we assume that the integers Modulo p form a group. Then every element has its inverse in the group, but the only cases of X^2 ==1 Mod p are X=1 and X=-1.

    So the product (p-1)! Modulo p, links every element with its inverse except 1 and -1, so the product comes out: [tex] (p-1)! \equiv -1 Mod p[/tex]

    Now if we go on with that, if we split the group into (p-1)/2 successive groups of integers, then we have: [tex](p-1)! \equiv {((p-1)/2)!}^2 *(-1)^_(p-1)/2 [/tex] Consequently if p is congruent to 1 Mod 4, then there is an X such that X^2==(p-1)! ==-1 Mod p.
     
    Last edited: May 29, 2005
  13. May 29, 2005 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Use the Legendre symbol:

    If -1 does not have a square root, then (-1/p) = -1.
    Since the symbol is multiplicative, we have (-m/p) = (-1/p)(m/p) = -(m/p), so that one of the two must be 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Show reducibility
  1. Reduced homology (Replies: 3)

  2. Reducing numbers (Replies: 4)

  3. Reducing to a matrix (Replies: 0)

Loading...