# Irreducibility in Zp

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

## Answers and Replies

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

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