Results 1 to 5 of 5

Thread: 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
    21,796
    Thanks
    2827
    Awards
    1
    Consider the fact that $\displaystyle \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 $\displaystyle \left( {\begin{array}{c} p \\ k \\ \end{array}} \right),\;k \in \left\{ {1,2, \cdots ,p - 1} \right\}$.

    $\displaystyle \left( {a + b} \right)^p = \sum\limits_{k = 0}^p {\left( {\begin{array}{c}
    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,656
    Thanks
    14
    Of course

    $\displaystyle \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
    5
    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

    $\displaystyle \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: Apr 22nd 2010, 02:50 PM
  2. Congruence proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Nov 10th 2009, 10:03 AM
  3. A Congruence Proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Jun 5th 2009, 09:34 AM
  4. another congruence proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Feb 19th 2009, 02:41 PM
  5. Congruence proof
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Mar 24th 2008, 07:16 AM

Search Tags


/mathhelpforum @mathhelpforum