Let p>0 be a prime number. prove that p divides the binomial coefficient
(p i)= p!/i!(p-i)! for each integer 0<i<p.
( p over i ) = P factorial over i factorial times (p minus i) factorial.
and use that to show that (a + b)^p= a^p+ b^p mod p
Let p>0 be a prime number. prove that p divides the binomial coefficient
(p i)= p!/i!(p-i)! for each integer 0<i<p.
( p over i ) = P factorial over i factorial times (p minus i) factorial.
and use that to show that (a + b)^p= a^p+ b^p mod p
For the first part note that $\displaystyle (p!)=p[(p-1)!]$ and $\displaystyle \left( {p - 1} \right)! = \prod\limits_{i = 1}^{p - 1} i $.
The result follows from those two observations.
Then note that $\displaystyle \left( {a + b} \right)^p = \sum\limits_{k = 0}^p {\binom{p}{k}} a^k b^{p - k} = a^p + b^p + \sum\limits_{k = 1}^{p - 1} {\binom{p}{k}} a^k b^{p - k} $
Hello,
To continue what Plato said, you should also know that a prime number has only 2 divisors : 1 and himself. Hence every integer in $\displaystyle \{2, 3, \dots, p-1 \}$ won't divide p.
So within the factors of $\displaystyle i!=2 \times 3 \times 4 \times \dots \times i$, knowing that $\displaystyle i<p$, is there any divisor of p ?
Within the factors of $\displaystyle (p-i)!$, knowing that $\displaystyle p-i<p$, is there any divisor of p ?
You can imagine that "p remains as a unique element and won't be divided/separated by anything in the denominator".
And I think that a bit of Gauss's lemma can help for the formal demonstration...
You have to prove that $\displaystyle p|{p \choose k}$(like Moo did), then you can continue in Plato's argument:
$\displaystyle \left(\sum\limits_{k = 1}^{p - 1} {\binom{p}{k}} a^k b^{p - k}\right) \,\, mod \, p = 0 $---------------------since $\displaystyle p|{\binom{p}{k}}$