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

 

[blue_raver22]

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.