'Euler criterion' for cube roots?

[Camila86]

I am trying to derive a version of Euler's criterion for the existence of cube roots modulo p, prime.

So far, I have split the primes up into two cases:

For p = 3k+2, every a(mod p) has a cube root.

For p = 3k+1, I don't know which a it is true for, but I did a few examples and noticed a couple of things:

* If a is a cube, so is -a
* If a is a cube, it has exactly 3 cube roots

Does this have anything to do with p-1= 0(mod3)?

 

[robert Ihnot]

For the form p=3k+2, three does not divide p-1, the order of the group, and so cubing the elements just permutates the residues, so every element (trivially) has a cube root.

Now in the case where 3 divides p-1, we have X^(p-1)/3 -1==0 Mod p and it will have (p-1)/3 elements that satisfy it. Proof:

X^(p-1)-1 =={X^(p-1)/3-1}{X^2(p-1)/3+X^(p-1)/3+1} Mod p, and since the left side has p-1 distinct solutions, (the entire multiplicative residue set), so does the other side and thus there are (p-1)/3 solutions to the first part of the right side. All of these can be shown to be cubes. Proof:

Let b^(p-1)/3 ==1 Mod p. b, itself, is a power of a primative root b=d^u. Since d^u(p-1)/3==1 Mod p, and p-1 is the smallest positive power such that this occurs it follows that u/3 is an integer, and so b is a cube.

Each cube has three roots. Proof: Firstly with all elements cubed we know that 2/3 of these cubes are duplicates. Give a^3==b^3 Mod p, either a==b or a^2+ab+b^2==0 Mod p. Here we make a transformation used by Euler: Let x+y=2a, x-y=2b, then the above equation transforms (1/4)(3X^2+Y^2==0 Mod p), thus there is a solution to (Y/X)^2== -3 Mod p. So there is a solution to

$$\beta=\frac{-1+\sqrt-3}{2}$$ This element represents the cube root of unity and so given a^3, have the three roots: $$a,a\beta, a\beta^2$$

 

[tacman]

The Euler criterion is a theorem in number theory that provides a necessary and sufficient condition for a quadratic residue to exist modulo a prime number. It states that if a is a quadratic residue modulo p, where p is an odd prime, then a^((p-1)/2) ≡ 1 (mod p). This criterion has been extended to higher powers, such as the Legendre symbol for cubic residues.

In your case, you are trying to derive a version of Euler's criterion for the existence of cube roots modulo p, where p is an odd prime. It is important to note that this version of the criterion is not a generalization of the original criterion, but rather a separate theorem.

Your approach of splitting the primes into two cases is a good start. For p = 3k+2, it is true that every a (mod p) has a cube root. This can be easily proven by using the fact that (p-1)/3 is an integer for p = 3k+2, and thus a^((p-1)/3) ≡ 1 (mod p) for any a (mod p).

For p = 3k+1, where p is congruent to 1 modulo 3, things get a bit more complicated. As you have noticed, if a is a cube, then so is -a. This is because (-a)^3 ≡ -(a^3) ≡ -a (mod p). However, this does not mean that every a (mod p) has a cube root.

In fact, it can be proven that if a is a cube (mod p), then it has exactly 3 cube roots. This can be seen by considering the numbers a^((p+1)/3), a^((p+1)/3) * ω, and a^((p+1)/3) * ω^2, where ω is a primitive cube root of unity modulo p. These three numbers are distinct and are all cubes (mod p), thus giving us the three cube roots of a (mod p).

To answer your question about the relationship between p-1 ≡ 0 (mod 3) and the existence of cube roots, it is worth noting that p-1 ≡ 0 (mod 3) implies that p is congruent to 1 modulo 3. This means that for any a (mod p), there will be