# Non-Divisbility of Binomial Coefficients of n by Prime

## Theorem

Let $n \in \Z_{\ge 0}$ be a positive integer.

Let $k \in \Z_{\ge 0}$ such that $0 \le k \le n$.

Let $p$ be a prime number.

Then:

- $\dbinom n k$ is not divisible by $p$

- $n = a p^m - 1$ where $1 \le a < p$

for some $m \in \Z_{\ge 0}$.

## Proof

The statement:

- $\dbinom n k$ is not divisible by $p$

is equivalent to:

- $\dbinom n k \not \equiv 0 \pmod p$

The corollary to Lucas' Theorem gives:

- $\displaystyle \dbinom n k \equiv \prod_{j \mathop = 0}^r \dbinom {a_j} {b_j} \pmod p$

where:

- $n, k \in \Z_{\ge 0}$ and $p$ is prime
- the representations of $n$ and $k$ to the base $p$ are given by:
- $n = a_r p^r + \cdots + a_1 p + a_0$
- $k = b_r p^r + \cdots + b_1 p + b_0$

Consider the form of $n = a p^m - 1$ when represented to the base $p$:

\(\displaystyle n\) | \(=\) | \(\displaystyle a p^m - 1\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle a \left({p^m - 1}\right) + \left({a - 1}\right)\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle a \left({p - 1}\right) \sum_{j \mathop = 0}^{m - 1} p^i + \left({a - 1}\right)\) | Sum of Geometric Progression: Corollary 1 | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \left({a - 1}\right) p^m + \sum_{j \mathop = 0}^{m - 1} \left({p - 1}\right) p^i\) | after algebra |

That is, all of the digits of $n$ are $p - 1$ except perhaps the first one.

For $k$ such that $0 \le k \le n$, the digits of $k$ will all range over $0$ to $p - 1$.

### Necessary Condition

Let $n = a p^m - 1$.

Then all the binomial coefficients $\dbinom {a_j} {b_j}$ (except perhaps the first) are of the form $\dbinom {p - 1} k$ for $0 \le k < p$.

By Binomial Coefficient of Prime Minus One Modulo Prime:

- $\dbinom {p - 1} k \equiv \left({-1}\right)^k \pmod p$

and so:

- $\dbinom {p - 1} k \equiv \left({-1}\right)^k \pmod p$

and so:

- $\displaystyle \prod_{j \mathop = 0}^r \dbinom {a_j} {b_j} \not \equiv 0 \pmod p$

### Sufficient Condition

Let $\dbinom n k$ not be divisible by $p$.

Aiming for a contradiction, suppose $n \ne a p^m - 1$.

Then one of the digits $a_j$ will be less than $p - 1$.

But the digits of all possible $k$ will range over $0$ to $p - 1$.

Therefore there must be at least one $\dbinom {a_j} {b_j}$ such that $b_j > a_j$.

Such a condition leads to $\dbinom {a_j} {b_j} = 0$.

That is:

- $\displaystyle \prod_{j \mathop = 0}^r \dbinom {a_j} {b_j} \equiv 0 \pmod p$

which means $\dbinom n k$ not be divisible by $p$.

From this contradiction it follows that $n = a p^m - 1$ for some $a \in \Z, 0 < a < p$ and $m \in \Z_{>0}$.

$\blacksquare$

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $12$