Editing Binomial coefficient (section)

== Divisibility properties ==
{{main|Kummer's theorem|Lucas' theorem}}
In 1852, [[Ernst Kummer|Kummer]] proved that if ''m'' and ''n'' are nonnegative integers and ''p'' is a prime number, then the largest power of ''p'' dividing <math>\tbinom{m+n}{m}</math> equals ''p''<sup>''c''</sup>, where ''c'' is the number of carries when ''m'' and ''n'' are added in base ''p''.
Equivalently, the exponent of a prime ''p'' in <math>\tbinom n k</math>
equals the number of nonnegative integers ''j'' such that the [[fractional part]] of ''k''/''p''<sup>''j''</sup> is greater than the fractional part of ''n''/''p''<sup>''j''</sup>. It can be deduced from this that <math>\tbinom n k</math> is divisible by ''n''/[[greatest common divisor|gcd]](''n'',''k''). In particular therefore it follows that ''p'' divides <math>\tbinom{p^r}{s}</math> for all positive integers ''r'' and ''s'' such that {{math|''s'' < ''p''<sup>''r''</sup>}}. However this is not true of higher powers of ''p'': for example 9 does not divide <math>\tbinom{9}{6}</math>.

A somewhat surprising result by [[David Singmaster]] (1974) is that any integer divides [[almost all]] binomial coefficients. More precisely, fix an integer ''d'' and let ''f''(''N'') denote the number of binomial coefficients <math>\tbinom n k</math> with ''n'' < ''N'' such that ''d'' divides <math>\tbinom n k</math>. Then
: <math> \lim_{N\to\infty} \frac{f(N)}{N(N+1)/2} = 1. </math>
Since the number of binomial coefficients <math>\tbinom n k</math> with ''n'' < ''N'' is ''N''(''N'' + 1) / 2, this implies that the density of binomial coefficients divisible by ''d'' goes to 1.

Binomial coefficients have divisibility properties related to least common multiples of consecutive integers. For example:<ref name="Farhi2007">{{cite journal |last=Farhi |first=Bakir |title=Nontrivial lower bounds for the least common multiple of some finite sequence of integers |journal=Journal of Number Theory |volume=125 |issue=2 |year=2007 |pages=393–411 |doi=10.1016/j.jnt.2006.10.017 |arxiv=0803.0290 |s2cid=115167580 }}</ref>
: <math>\binom{n+k}k</math> divides <math>\frac{\operatorname{lcm}(n,n+1,\ldots,n+k)}n</math>.
: <math>\binom{n+k}k</math> is a multiple of <math>\frac{\operatorname{lcm}(n,n+1,\ldots,n+k)}{n\cdot \operatorname{lcm}(\binom{k}0,\binom{k}1,\ldots,\binom{k}k)}</math>.

Another fact:
An integer {{math|''n'' ≥ 2}} is prime if and only if
all the intermediate binomial coefficients
: <math> \binom n 1, \binom n 2, \ldots, \binom n{n-1} </math>
are divisible by ''n''.

Proof:
When ''p'' is prime, ''p'' divides
: <math> \binom p k = \frac{p \cdot (p-1) \cdots (p-k+1)}{k \cdot (k-1) \cdots 1} </math> for all {{math|1=0 < ''k'' < ''p''}}
because <math>\tbinom p k</math> is a natural number and ''p'' divides the numerator but not the denominator.
When ''n'' is composite, let ''p'' be the smallest prime factor of ''n'' and let {{math|1=''k'' = ''n''/''p''}}. Then {{math|1=0 < ''p'' < ''n''}} and
: <math> \binom n p = \frac{n(n-1)(n-2)\cdots(n-p+1)}{p!}=\frac{k(n-1)(n-2)\cdots(n-p+1)}{(p-1)!}\not\equiv 0 \pmod{n}</math>
otherwise the numerator {{math|1=''k''(''n'' − 1)(''n'' − 2)⋯(''n'' − ''p'' + 1)}} has to be divisible by {{math|1=''n'' = ''k''×''p''}}, this can only be the case when {{math|1=(''n'' − 1)(''n'' − 2)⋯(''n'' − ''p'' + 1)}} is divisible by ''p''. But ''n'' is divisible by ''p'', so ''p'' does not divide {{math|1=''n'' − 1, ''n'' − 2, …, ''n'' − ''p'' + 1}} and because ''p'' is prime, we know that ''p'' does not divide {{math|1=(''n'' − 1)(''n'' − 2)⋯(''n'' − ''p'' + 1)}} and so the numerator cannot be divisible by ''n''.