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

Question

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?

Answer 1

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.