# Number theory proof

1. Mar 2, 2007

### ElDavidas

1. The problem statement, all variables and given/known data

Let $p$ be a prime number such that $p \equiv 1 (mod 3)$

Let $a$ be an integer not divisible by $p$. Show that if the congruence $x^3 \equiv a (mod p)$ has a solution then

$$a^{\frac{p - 1} {3}} \equiv 1 (mod p)$$

3. The attempt at a solution

Right, I'm not sure how to prove this. I've got a couple of ideas at how things might relate to one another.

I can see that $gcd(a,p) = 1$ and also that

$\frac{p-1}{3} = k$ for some integer k. I think this relates to the power of a in the equation.

$$a^{\frac{p - 1} {3}} \equiv 1 (mod p)$$.

Could you also apply fermat's little theorem in some way to this?

Also, I don't know what to do with $x^3 \equiv a (mod p)$.

Could someone give me a hint or two in how to prove this? It would be much appreciated.

Thanks

Last edited: Mar 2, 2007
2. Mar 2, 2007

### tim_lou

hint:
$$x^{p-1}\equiv 1 \mod{p}$$
by Fermat's little theorem.

not enough?
what is $$x^{p-1}$$ equivalent to in terms of a?

Last edited: Mar 2, 2007
3. Mar 2, 2007

### Dick

Substitute x^3 for a in your congruence. And, yes, use Fermat's little theorem.

4. Mar 2, 2007

### ElDavidas

ok, so far my solution is as follows:

$x^3 \equiv a (mod p)$

Then $x \equiv a^{\frac{1}{3}} (mod p)$

So by Fermat, $x^{p-1} \equiv 1 (mod p)$ or

$$a^{\frac{1(p-1)}{3}} \equiv 1 (mod p)$$

Would I need to say $gcd (x,p) = 1$? If so, how is this true?

5. Mar 2, 2007

### Dick

Clearly, yes, you need to show gcd(x,p)=1! How might that be possible?

6. Mar 2, 2007

### ElDavidas

I'm not sure. Could you use the Euclidean Algorithm? I've also been trying to find a contradiction by assuming that $gcd (x,p) \neq 1$.

7. Mar 2, 2007

### Dick

p is a prime. gcd(a,p)=1 says p does not divide a. Is it possible for p to divide x?

8. Mar 2, 2007

### ElDavidas

Ah, I see now! Thanks.