Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook