nLab
freshman's dream

Context

Arithmetic

  • ,

  • ,

  • , , , , , , , , , , ,

  • ,

  • , ,

  • , , ,

,

    • ,

Contents

Idea

Over a ring whose characteristic is a prime number pp it is true that

(a+b) p=a p+b p, (a+b)^p = a^p + b^p \,,

because all the non-trivial binomial coefficients are multiples of pp.

Primality

Lemma

An integer n2n \geq 2 is prime if and only if the binomial coefficients satisfy

(nk)0(modn)\binom{n}{k} \equiv 0 \pmod{n}

whenever 0<k<n0 \lt k \lt n.

Proof

If pp is prime, then pp divides neither k!k! nor (pk)!(p-k)! if 0<k<p0 \lt k \lt p. So, since pp divides

p!=(pk)k!(pk)!,p! = \binom{p}{k}k! \cdot (p-k)!,

it must divide (pk)\binom{p}{k}.

If nn is composite, write n=pqn = p q where pp is any prime dividing nn, so that 0<p<n0 \lt p \lt n. If the factor pp appears with multiplicity jj in nn, then it appears with multiplicity jj in n(n1)(np+1)n(n - 1) \ldots (n - p + 1) and with multiplicity 11 in p!=p(p1)1p! = p(p-1)\ldots 1, and so it appears with multiplicity j1j-1 in (np)\binom{n}{p}. It follows that nn cannot divide (np)\binom{n}{p}, i.e., (np)0(modn)\binom{n}{p} \nequiv 0 \pmod{n}.

References

Last revised on March 16, 2017 at 10:18:06. See the history of this page for a list of all contributions to it.