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

• Bachelier
In summary, x^2+1 has a root in Zp, is equivalent to having an element of order 4 in Zp^x if x is a prime. This means that for some prime p, x^2+1 will not have a solution if x is not a prime.

#### 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

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.

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

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

Zp^x refers to the set of all elements in the field Zp that have a multiplicative inverse. In other words, it is the set of all non-zero elements in Zp. This is important because in order to have a multiplicative inverse, an element must have a non-zero remainder when divided by p (the modulus).

The order of an element in Zp refers to the smallest positive integer n such that a^n is congruent to 1 modulo p. In other words, it is the smallest exponent that results in the element being congruent to 1 when multiplied by itself. For example, in Z5, the order of 2 would be 4 because 2^4 is congruent to 1 modulo 5.

Now, when we consider the equation x^2+1 having a root in Zp, it means that there exists an element in Zp that satisfies the equation and has a multiplicative inverse. This is equivalent to saying that the element has an order of 4 in Zp^x. This is because the element must have an order that is a divisor of p-1 (Fermat's Little Theorem). Since p is a prime number, the only divisors of p-1 are 1, 2, and p-1. Therefore, the order of the element must be either 1, 2, or p-1. However, since we know that the element has a multiplicative inverse, its order cannot be 1 or p-1, leaving 2 as the only possibility. This means that the element must have an order of 4 in Zp^x.

In the case of Z5, both 2 and 3 satisfy the equation x^2+1, but only 3 has an order of 4 in Zp^x. This is because 3^4 is congruent to 1 modulo 5, while 2^4 is congruent to 16, which is not congruent to 1. So, while both 2 and 3 are solutions to the equation x^2+1, only 3 has an order of 4 in Zp^x.

I hope this helps to clarify the concept of irreducibility in Zp and the order of elements in Zp. If you have any further questions or need more clarification, please let me know.

## 1. What does Zp^x represent?

Zp^x represents the multiplicative group of integers modulo p, where p is a prime number. This group consists of all integers between 1 and p-1 that are relatively prime to p.

## 2. How is Zp^x related to irreducibility in Zp?

Zp^x is closely related to the concept of irreducibility in Zp. An element a in Zp is considered irreducible if it has no divisors in Zp, other than 1 and itself. The order of a in Zp^x is equal to the order of a in Zp, which can help determine if a is irreducible.

## 3. What is the order of an element in Zp^x?

The order of an element a in Zp^x is the smallest positive integer n such that a^n is congruent to 1 modulo p. In other words, it is the smallest exponent that results in a being equivalent to 1 when multiplied by itself n times.

## 4. How can the order of an element in Zp^x be calculated?

The order of an element a in Zp^x can be calculated using the Euler totient function, φ(p), where p is the prime modulus. The order of a is equal to the smallest number k such that a^k ≡ 1 (mod p). This can also be calculated using prime factorization, where the order of a is equal to the least common multiple of the orders of its prime factors.

## 5. Can the order of an element in Zp^x be greater than p-1?

No, the order of an element in Zp^x cannot be greater than p-1 because the multiplicative group of Zp^x has p-1 elements. This means that the largest possible order of an element in Zp^x is p-1, which occurs when the element is a generator of the group.