binomial coefficients are integers because numerator and denominator form pairs?

Question

I've heard of a claim that when calculating the binomial formula with integer input:

$\mathrm{Bin}(n,k):=\prod^k_{i=1}\frac{n+1-i}{i}\in \mathbb{N}\ (\forall n,k\in\mathbb N)$

each denominator divides an unique numerator. since for calculating $n \choose k$ you divide $k$ many numerators ($n+1-k$ till $n$) by $k-1$ many denominators (numbers from $2$ to $k$), there obviously is a gap, where is it?

$\mathrm{Gap}(n,k):=\sum_{j=0}^{k-1}(n-j)-\sum^k_{i=2} n-(n \mod\ i)$

Remember, $n\mod i$ denotes the remainder from dividing $n$ by $i$. that means $i$ divides $n - (n \mod\ i)$. above formula $\mathrm{Gap}(n,k)$ just sums up all such expressions and calculates the number which isn't paired with a divisor. any other way to calculate this? the first sum has an explicit formula making it into a quadratic polynomial in $k$. anything known about the 2nd sum? did I make a mistake here?

I'd be already satisfied if someone could prove above claim that reason for the product $\mathrm{Bin}(n,k)$ of rational numbers being an integer is because there are pairs of numerator and denominator which are integers after the division, and that in such pairing no numerator is ever used twice.

Answer 1

The kind of pairing sought does not always exist. Take, for example, $$\binom{8}{4}=\frac{8\cdot7\cdot6\cdot5}{4\cdot3\cdot2\cdot1}.$$ The pair of $4$ must be $8$, the pair of $3$ must be $6$, and hence the pair of $2$ should be $7$ or $5$ which is not good.

On the other hand, it is possible to prove using unique factorization that the binomial coefficients are integers. Namely, for each prime $p$, one can show that the exponent of $p$ in $n!$ is at least the exponent of $p$ in $k!(n-k)!$. For more details, see here and here.