Prove that if $p$ is a prime, then $p$ is a factor of $\binom{p}{r}$ for $r=1,2,\dots,p-1$ by using induction. Prove that if $p$ is a prime, then $p$ is a factor of $\binom{p}{r}$ for $r=1,2,\dots,p-1$ by using induction.
First, $\binom{p}{1}=p$. So it is clear that it has factor $p$.
Suppose that $\binom{p}{k}$ has factor $p$ for some $k\geq1$.
Then $$\binom{p}{k+1}=\frac{p-k}{k+1}\binom{p}{k}$$
Here, I can't think of how to use the induction hypothesis since $\frac{p-k}{k+1}$ is not necessarily an integer.
 A: Rewrite as $(k+1)\binom{p}{k+1}=(p-k)\binom{p}{k}$.
Note that $p$ divides the right-hand side, and does not divide $k+1$, so it must divide $\binom{p}{k+1}$.
A: You are off to a good start, here is a hint for how to continue.
Multiply your equation by $k+1$ to give
$$(k+1)\binom{p}{k+1}=(p-k)\binom pk\ .$$
By assumption $p\mid RHS$, so $p\mid LHS$.  But $p\not\mid k+1$ because . . . and therefore 
$$p\mid\binom{p}{k+1}$$
because . . .
See if you can fill in the reasons indicated by dots.
A: If you use a recursive definition of $\binom{p}{r}$ then this is easy to show via the definition of a prime.  The explicit formula is:
$$
\binom{p}{r} = \frac{p!}{(p-r)!r!} \\
\binom{p}{r+1} = \frac{p!}{(p-r-1)!(r+1)!} = \frac{p!}{(p-r)!r!}\frac{p - r}{r+1}
$$
$$
\binom{p}{r+1} = \binom{p}{r}\frac{p-r}{r+1}
$$
So start with your base case:
$$
\binom{p}{1} = p
$$
This clearly is divisible by $p$.  Now use the inductive step.  If $p$ is prime and $\binom{p}{r}$ is divisible by $p$, then $\binom{p}{r+1}$ must also be divisible by $p$:
This is because we have $\binom{p}{r+1} = \binom{p}{r}\frac{p - r}{r+1}$--therefore the only way that $\binom{p}{r+1}$ is not divisible by $p$ is if $r+1$ is can "break down" $p$. I.e. that $r + 1$ shares a factor of $p$--which is not possible by the definition of prime $p$ (along with the fact that we are saying $r + 1 < p$).
I want to make this concrete, let's say we have $p = 12$ (not prime). Eventually this number will be broken down (will be divided): when $r + 1 = 2$ and (possibly) again when $r + 1= 3, 4, 6$. I don't know whether or not $2^{12} - 2$ is divisible by $12$ or not--all I can say is that I'm "not sure".
On the other hand if I choose $p = 11$ (a prime). I know that none of the numbers below $11$ can divide it and thus every "middle" number in Pascal's triangle must be divisible by $11$...therefore $2^{11} - 2$ is divisible by $11$ and likewise $2^{11} - 2 = 2(2^{10} - 1)$ must also be--therefore $n$ divides $2^{n - 1} - 1$ if $n$ is prime (which is a very small part of Fermat's little theorem).
