1. Limited time only! Sign up for a free 30min personal 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!

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.

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


    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


    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


    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