1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number theory proof

  1. Mar 2, 2007 #1
    1. The problem statement, all variables and given/known data

    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]



    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 [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: Mar 2, 2007
  2. jcsd
  3. Mar 2, 2007 #2
    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: Mar 2, 2007
  4. Mar 2, 2007 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Substitute x^3 for a in your congruence. And, yes, use Fermat's little theorem.
     
  5. Mar 2, 2007 #4
    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?
     
  6. Mar 2, 2007 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Clearly, yes, you need to show gcd(x,p)=1! How might that be possible?
     
  7. Mar 2, 2007 #6
    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].
     
  8. Mar 2, 2007 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    p is a prime. gcd(a,p)=1 says p does not divide a. Is it possible for p to divide x?
     
  9. Mar 2, 2007 #8
    Ah, I see now! Thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Number theory proof
  1. Number Theory Proofs (Replies: 6)

Loading...