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?

  • 5
    $\begingroup$ 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. $\endgroup$ Feb 19 '18 at 18:17
  • 1
    $\begingroup$ If $i=0$ or $i=n$, this is not true, of course. $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.