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: Proof of Fermat's Theorm

  1. Jun 21, 2014 #1
    1. The problem statement, all variables and given/known data
    In proving Fermats Theorm, I got confused trying to follow one of the steps.

    Theorm: If p is prime, then:
    a^p~a (mod p).

    part of proof:
    multiply all the nonzero elements in Z_p by a to obtain
    These are all distinct elements and none equal [0], so they must be the set of all nonzero elements [1],[2],....,[p-1] in some order. In particular, the products are the same and we obtain
    ([a]^(p-1))([1],[2],....,[p-1]) = ([1],[2],....,[p-1])

    That fact that those last parts equal eachother is confusing me, help?

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Jun 21, 2014 #2
    Don't you mean ([a]^(p-1))([1][2]....[p-1]) = ([1][2]....[p-1])?

    And if that is what you mean, does your question still stand?
  4. Jun 21, 2014 #3
    Firstly, you can consider Euler's theorem too.
    So we know that the set Q = { a*a_1 , a*a_2, .., a*a_p-1 } includes all elements in the set B = {a_1, a_2, .., a_p-1 } in mod p.
    We know that from the property that
    " if (a,p) = 1, we can get rid of the a in the equation :
    a*a_i = a*a_j (mod p) ⇔ a_i = a_j (mod p) "

    Which means that all elements in Q are distinct. And they are equal to one and only one of the elements in B.

    So we get

    (a*a_1) * (a*a_2) * .. * (a*a_p-1 ) = a_1 * a_2 *..* a_p-1 (mod p)
    a^(p-1) * A = A (mod p)
    a^(p-1) = 1 (mod p).

    end of the proof.
  5. Jun 21, 2014 #4
    In addition to what is said above, you will need to state this restriction on the part you are doing: ##p## does not divide ##a##, or ##p \nmid a##.

    The case of p divides a, ##p \mid a##, will need to be discussed separately.
  6. Jun 21, 2014 #5
    As I told above;
    " if (a,p) = 1, we can get rid of the a in the equation :
    a*a_i = a*a_j (mod p) ⇔ a_i = a_j (mod p) "
    you can't get rid of a if you don't have (a,p) = 1 property. And that prop. is given in the theorem.
  7. Jun 21, 2014 #6
    This is true, it may be given in the assignment since this case is trivial.

    OP, the key here is that if p is prime, and a and b are both not multiples of p, then ab is not a multiple of p. Do you see why this makes the left product one of p-1 distinct classes none of which are [0]?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted