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.