Number theory proof

  • Thread starter ElDavidas
  • Start date
  • #1
80
0

Homework Statement



Let [itex] p [/itex] be a prime number such that [itex]p \equiv 1 (mod 3) [/itex]

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

[tex] a^{\frac{p - 1} {3}} \equiv 1 (mod p) [/tex]



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 [itex]gcd(a,p) = 1[/itex] and also that

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

[tex] a^{\frac{p - 1} {3}} \equiv 1 (mod p) [/tex].

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

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

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

Thanks
 
Last edited:

Answers and Replies

  • #2
682
1
hint:
[tex]x^{p-1}\equiv 1 \mod{p}[/tex]
by Fermat's little theorem.





not enough?
what is [tex]x^{p-1}[/tex] equivalent to in terms of a?

try contradiction.
 
Last edited:
  • #3
Dick
Science Advisor
Homework Helper
26,260
619
Substitute x^3 for a in your congruence. And, yes, use Fermat's little theorem.
 
  • #4
80
0
ok, so far my solution is as follows:

[itex] x^3 \equiv a (mod p)[/itex]

Then [itex] x \equiv a^{\frac{1}{3}} (mod p)[/itex]

So by Fermat, [itex] x^{p-1} \equiv 1 (mod p)[/itex] or

[tex] a^{\frac{1(p-1)}{3}} \equiv 1 (mod p)[/tex]

Would I need to say [itex] gcd (x,p) = 1[/itex]? If so, how is this true?
 
  • #5
Dick
Science Advisor
Homework Helper
26,260
619
ok, so far my solution is as follows:

[itex] x^3 \equiv a (mod p)[/itex]

Then [itex] x \equiv a^{\frac{1}{3}} (mod p)[/itex]

So by Fermat, [itex] x^{p-1} \equiv 1 (mod p)[/itex] or

[tex] a^{\frac{1(p-1)}{3}} \equiv 1 (mod p)[/tex]

Would I need to say [itex] gcd (x,p) = 1[/itex]? If so, how is this true?
Clearly, yes, you need to show gcd(x,p)=1! How might that be possible?
 
  • #6
80
0
I'm not sure. Could you use the Euclidean Algorithm? I've also been trying to find a contradiction by assuming that [itex] gcd (x,p) \neq 1 [/itex].
 
  • #7
Dick
Science Advisor
Homework Helper
26,260
619
p is a prime. gcd(a,p)=1 says p does not divide a. Is it possible for p to divide x?
 
  • #8
80
0
Ah, I see now! Thanks.
 

Related Threads on Number theory proof

  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
24
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
2
Views
3K
Top