Results 1 to 5 of 5

Math Help - Proof congruence

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    21

    Proof congruence

    Show that if p is a prime, then (a + b)^p ≡ a^p + b^p (mod p)
    (Hint: prove and use that p choose k is a multiple of p for every k ∈ {1, . . . , p − 1}). Then expand (a + b)^p via the binomial theorem).
    Using the previous formula, prove Fermatís little Theorem (in its equivalent form, a^p ≡ a (mod p)) by induction on a.

    Any help appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,965
    Thanks
    1784
    Awards
    1
    Consider the fact that \left( {\begin{array}{c}    p  \\    k  \\ \end{array}} \right) = \frac{{p!}}{{k!\left( {p - k} \right)!}}\;,\;k \in \left\{ {1,2, \cdots ,p - 1} \right\}.
    Then note that because p is prime neither k! nor (p-k)! is a factor of p.
    So p is a factor of \left( {\begin{array}{c}    p  \\     k  \\ \end{array}} \right),\;k \in \left\{ {1,2, \cdots ,p - 1} \right\}.

    \left( {a + b} \right)^p  = \sum\limits_{k = 0}^p {\left( {\begin{array}{c}<br />
   p  \\    k  \\ \end{array}} \right)a^{p - k} b^k }  = a^p  + \sum\limits_{k = 1}^{p - 1} {\left( {\begin{array}{c}    p  \\    k  \\ \end{array}} \right)a^{p - k} b^k }  + b^P .

    Can you see how to complete the argument?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    You can use {p\choose k} to save time.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Math Engineering Student
    Krizalid's Avatar
    Joined
    Mar 2007
    From
    Santiago, Chile
    Posts
    3,654
    Thanks
    14
    Of course

    \binom pk made it with \binom pk.

    (The space is necessary, but when using numbers, for example, \binom23 there's no problem.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ThePerfectHacker View Post
    You can use {p\choose k} to save time.
    this is what i always use

    Quote Originally Posted by Krizalid View Post
    Of course

    \binom pk made it \binom pk.

    (The space is necessary, but when using numbers, for example, \binom23 there's no problem.)
    this is nice!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 22nd 2010, 03:50 PM
  2. Congruence proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 10th 2009, 11:03 AM
  3. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 5th 2009, 10:34 AM
  4. another congruence proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 19th 2009, 03:41 PM
  5. Congruence proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 24th 2008, 08:16 AM

Search Tags


/mathhelpforum @mathhelpforum