Understand Irreducibility in Zp: What is Zp^x? Order of Elements in Zp

[Bachelier]

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

 

[Citan Uzuki]

Do you mean \mathbb{Z}_{p}^{\times}? This is just the group of invertible elements of \mathbb{Z}_{p} under multiplication. So in \mathbb{Z}_{5}^{\times}, 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.

 

[Deveno]

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

addition mod p
multiplication mod p.

it just so happens that Z_p - {0} (this is what is meant by (Z_p)^x. for a general n, it means only the elements in Z_n, 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 (Z₇)^x (everything is mod 7)

1 has order 1.
2² = 4
2³ = 1, 2 has order 3.

3²= 2
3³= 6
3⁴= 4
3⁵= 5
3⁶= 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.

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

1²+1 = 2
2²+1 = 5
3²+1 = 3
4²+1 = 3
5²+1 = 5
6²+1 = 2

in fact, for Z_p to have a root of x²+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).

 

[Bachelier]

Both Thank you so much.

Deveno, How do I prove your last result. For Z_p 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).