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

Irreducibility in Zp

  1. Oct 29, 2011 #1
    I came across this while doing some research. Can someone help me understand this concept.

    x^2+1 has a root in Zp, is equivalent to having an element of order 4 in Zp^x

    First, what is Zp^x,
    Second are we considering the order under the multiplicative operation. So in this case, if I consider Z5, then no element has order 4 yet x= 2, and x =3 are both solution for x^2+1 !!

    thanks
     
  2. jcsd
  3. Oct 29, 2011 #2
    Do you mean [itex]\mathbb{Z}_{p}^{\times}[/itex]? This is just the group of invertible elements of [itex]\mathbb{Z}_{p}[/itex] under multiplication. So in [itex]\mathbb{Z}_{5}^{\times}[/itex], for instance, 2 has order 4 (since 2^4 = 1 mod 5, but 2^2 = 4 ≠ 1 mod 5.

    As for the other statement, if x^2 + 1 = 0, then x^2 = -1, so x^4 = 1 but x^2 does not, so x has order 4. Conversely, if x has order 4, then x^4 = 1, so x^2 = 1 or -1, but x^2 ≠ 1 since x does not have order 2, hence x^2 = -1 and is a root of x^2 + 1.
     
  4. Oct 29, 2011 #3

    Deveno

    User Avatar
    Science Advisor

    for a prime p, Zp has two operations we can consider.

    addition mod p
    multiplication mod p.

    it just so happens that Zp - {0} (this is what is meant by (Zp)x. for a general n, it means only the elements in Zn, co-prime to n, but with a prime, this is every non-zero element) also forms a group, under multiplication mod p.

    thus we can speak of order, just as we can with any group.

    for example, in (Z7)x (everything is mod 7)

    1 has order 1.
    22 = 4
    23 = 1, 2 has order 3.

    32= 2
    33= 6
    34= 4
    35= 5
    36= 1, 3 has order 6 (3 is a "primitive root", a generator)

    similarly, 4 has order 3, 5 has order 6 (another "primitive root"), and 6 has order 2.

    (Z7)x has no elements of order 4, which means we don't have any solutions of x2+1 = 0, which we can verify:

    12+1 = 2
    22+1 = 5
    32+1 = 3
    42+1 = 3
    52+1 = 5
    62+1 = 2

    in fact, for Zp to have a root of x2+1, p must be a prime of the form 4k+1, for some positive integer k (none of the primes of the form 4k+3 will work).
     
  5. Oct 29, 2011 #4
    Both Thank you so much.

    Deveno, How do I prove your last result. For Zp to have a root of x2+1, p must be a prime of the form 4k+1, for some positive integer k (none of the primes of the form 4k+3 will work).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Irreducibility in Zp
  1. Is this irreducible? (Replies: 4)

Loading...