# 'Euler criterion' for cube roots?

1. Mar 26, 2007

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

2. Mar 26, 2007

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

Last edited: Mar 27, 2007