Results 1 to 5 of 5

Math Help - Prove: For ever prime p and integer a, a^p is congruent to a (mod p)

  1. #1
    Newbie
    Joined
    Nov 2006
    Posts
    12

    Prove: For ever prime p and integer a, a^p is congruent to a (mod p)

    Well, I have noticed that for every integer a in a prime mod p, a^(p - 1) is congruent to 1 (mod p). I don't know why this is though, and if I had a proof for it, I could use the multiplicative property of congruency to show a^p is congruent to a (mod p). What should I do?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Geoffrey View Post
    Well, I have noticed that for every integer a in a prime mod p, a^(p - 1) is congruent to 1 (mod p). I don't know why this is though, and if I had a proof for it, I could use the multiplicative property of congruency to show a^p is congruent to a (mod p). What should I do?
    The name of this result was discovered by my favorite mathemation, Fermat.
    "Fermat's Little Theorem"

    I have 3 proofs.

    1 uses congruences and Pigeonhole Principle.

    1 uses Lagrange's Theorem from Group Theory.

    1 is my own proof using induction and alchemy.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2006
    Posts
    12
    May I see the first one that uses congruences and the pigeonhole principle? I really am unsure about how to go about that one.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by Geoffrey View Post
    May I see the first one that uses congruences and the pigeonhole principle? I really am unsure about how to go about that one.
    Let p prime and a an integer such as \gcd(a,p)=1.
    Consider the integers,
    1a,2a,3a,...,(p-1)a
    Now two are congruent to each other for that will yield,
    ra\equiv ka (\mbox{mod }p)
    Since, \gcd(a,p)=1 division yields,
    r\equiv k (\mbox{mod }p)
    Which is impossible for r\not = k and  1 \leq r,k\leq p-1 so they have different remainders.

    Thus,
    1a,2a,3a,....,(p-1)a form "a complete set of residues".
    What does that mean?
    Well it means,
    1a\equiv r_1
    2a\equiv r_2
    3a\equiv r_3
    ...
    (p-1)a\equiv r_{p-1}
    Where r_1,r_2,...,r_{p-1} are the remainders they leave.

    But by Dirichelt's Pigeonhole Principle they are the integers 1,2,3,...,p-1 (not necessarily in that order).

    Multiply these congruences,
    \prod_{k=1}^{p-1} k a\equiv \prod_{k=1}^{p-1}r_k (\mbox{mod }p)

    But, \prod_{k=1}^{p-1}r_k=(p-1)! (as explained before).

    Thus,
    (p-1)! a^{p-1}\equiv (p-1)! (\mbox{mod }p)
    Also, \gcd((p-1)!,p)=1
    Division yields,
    a^{p-1}\equiv 1(\mbox{mod }p)
    Q.E.D.
    (Applause)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2006
    Posts
    12
    Okay, I finally got it. We have very similar proofs, but I rely more on properties I've previously discovered about modulus on other homework sets. Thank you so much for your help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 22nd 2011, 12:37 PM
  2. Replies: 6
    Last Post: March 14th 2011, 07:06 AM
  3. [SOLVED] Every prime > 3 is congruent to \pm 1 mod 6
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: July 16th 2010, 06:50 AM
  4. prove a congruent angle with a bisector
    Posted in the Geometry Forum
    Replies: 2
    Last Post: June 18th 2007, 02:12 PM
  5. Replies: 4
    Last Post: November 12th 2006, 05:09 PM

Search Tags


/mathhelpforum @mathhelpforum