# Number theory proof

• ElDavidas
In summary, the problem states that given a prime number p that is congruent to 1 modulo 3, and an integer a that is not divisible by p, if the congruence x^3 is equivalent to a modulo p has a solution, then a^(p-1)/3 is also equivalent to 1 modulo p. The solution involves using Fermat's little theorem and the assumption that gcd(x,p) does not equal 1. By contradiction, it is shown that gcd(x,p) cannot be greater than 1, thus proving the solution.

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

Last edited:
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:
Substitute x^3 for a in your congruence. And, yes, use Fermat's little theorem.

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?

ElDavidas said:
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?

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

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

Ah, I see now! Thanks.