Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

'Euler criterion' for cube roots?

  1. Mar 26, 2007 #1
    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. jcsd
  3. Mar 26, 2007 #2
    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

    [tex]\beta=\frac{-1+\sqrt-3}{2}[/tex] This element represents the cube root of unity and so given a^3, have the three roots: [tex] a,a\beta, a\beta^2 [/tex]
    Last edited: Mar 27, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook