Proving Number Theory: Prime Numbers and Congruences

[ElDavidas]

Homework Statement

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

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

 

[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?

try contradiction.

 

[Dick]

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

 

[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?

 

[Dick]

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?

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

 

[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$.

 

[Dick]

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

 

[ElDavidas]

Ah, I see now! Thanks.