# How to prove that if $n$ is prime then ${{n}\choose{i}} = 0 \mod{n}$?

Within the proof of the AKS primality test, found here (page 2, Lemma 2.1), the author uses the fact that for prime $n$ we have $${{n}\choose{i}} = 0 \mod{n}$$

This assertion is a major part of the proof, but for some reason has not been proven itself. Is it a famous existing theorem, or do they have no excuse for not proving this assertion?

If this is not a theorem with a name and proof, could anyone please offer a proof of this?

EDIT: What about on the next line of the proof, where it says that if $n$ is composite, $q$ is prime, and $q^k || n$, then $q^k$ is coprime to $a^{n-q}$. What is the proof of this?

• This is well known. For one of may proofs, look at the formula for the binomial coefficient. It will have an uncancellable $n$ in the numerator. Feb 19 '18 at 18:17
• If $i=0$ or $i=n$, this is not true, of course.
– user436658
Feb 19 '18 at 18:19

Trivial case: $i \in \{0, n\}$. Otherwise, note that
$$\binom{n}{i} = \frac{n!}{(n - i)! i!}$$
is an integer. The numerator $n!$ is divisible by $n$, while the denominator $(n - i)! i!$ is not: all its prime divisors are at most $\max\{n - i, i\} < n$. So there is a factor of $n$ which is not canceled in the denominator.