# Numbers with Square-Free Binomial Coefficients/Lemma

## Theorem

Let $n$ be a (strictly) positive integer.

Let $p$ be a prime number.

By Basis Representation Theorem, there is a unique sequence $\sequence {a_j}_{0 \mathop \le j \mathop \le r}$ such that:

$(1): \quad \displaystyle n = \sum_{k \mathop = 0}^r a_k p^k$
$(2): \quad \displaystyle \forall k \in \closedint 0 r: a_k \in \N_b$
$(3): \quad r_t \ne 0$

Suppose $r \ge 2$ and $p^2 \nmid \dbinom n m$ for all $0 \le m \le n$.

Then:

$p^{r - 1} \divides \paren {n + 1}$

that is:

$p^{r - 1}$ divides $\paren {n + 1}$.

## Proof

Suppose $\forall i: 0 \le i \le r - 2: a_i = p - 1$.

Then:

 $\displaystyle n + 1$ $=$ $\displaystyle 1 + \sum_{i \mathop = 0}^r a_ip^i$ from $\displaystyle n = \sum_{k \mathop = 0}^r a_k p^k$ $\displaystyle$ $=$ $\displaystyle 1 + a_r p^r + a_{r - 1} p^{r - 1} + \sum_{i \mathop = 0}^{r - 2} (p - 1) p^i$ from $a_i = p - 1$ for all $0 \le i \le r - 2$ $\displaystyle$ $=$ $\displaystyle 1 + a_r p^r + a_{r - 1} p^{r - 1} + \paren {p^{r - 1} - 1}$ by Difference of Two Powers $\displaystyle$ $=$ $\displaystyle p^{r - 1} \paren {p a_r + a_{r - 1} + 1}$ factorisation

Since $p a_r + a_{r - 1} + 1$ is an integer,

we have $p^{r - 1} \divides \paren {n + 1}$.

Now we prove the contrapositive of our theorem.

Suppose $r > 2$ and $p^{r - 1} \nmid \paren {n + 1}$.

By the contrapositive of the result above:

$\exists i: 0 \le i \le r - 2, a_i \neq p - 1$

Let $I$ be the smallest integer for which $a_I \neq p - 1$.

Then for every $0 \le i < I$, we have:

$a_i = p - 1$

Let $m = p^r - 1$.

Then $m = \paren{p - 1} \displaystyle \sum_{i \mathop = 0}^r p^i$ is a representation of $m$ to the base $p$.

We also have:

 $\displaystyle n - m$ $=$ $\displaystyle \sum_{i \mathop = 0}^r a_ip^i - \paren {p^r - 1}$ from $\displaystyle n = \sum_{k \mathop = 0}^t a_k p^k$ $\displaystyle$ $=$ $\displaystyle 1 - p^r + a_r p^r + \sum_{i = I}^{r - 1} a_i p^i + \sum_{i = 0}^{I - 1} (p - 1) p^i$ from $a_i = p - 1$ for all $0 \le i < I$ $\displaystyle$ $=$ $\displaystyle 1 + \paren {a_r - 1} p^r + \sum_{i = I}^{r - 1} a_i p^i + \paren {p^I - 1}$ by Difference of Two Powers $\displaystyle$ $=$ $\displaystyle \paren {a_r - 1} p^r + \sum_{i = I + 1}^{r - 1} a_i p^i + \paren {a_I + 1} p^I$

Notice that:

$0 \le a_r - 1 < p - 1$
$0 \le a_i < p$ for $I + 1 \le i \le r - 1$
$1 \le a_I + 1 < p - 1 + 1 = p$

So $\paren {a_r - 1} p^r + \displaystyle \sum_{i = I + 1}^{r - 1} a_i p^i + \paren {a_I + 1} p^I$ is a representation of $n - m$ to the base $p$ (possibly with leading zeroes).

Now we add $n-m$ and $m$ in base $p$:

place value   p^r   p^{r-1}     p^{I+1}   p^I  p^{I-1} p^{I-2}       1
n - m =  (a_r-1) a_{r-1} ... a_{I+1} (a_I+1)   0       0    ...   0
+)     m =           (p-1)       (p-1)   (p-1)  (p-1)   (p-1)      (p-1)
-------------------------------------------------------------------------
n     =     *       *        a_{I+1}   a_I   (p-1)   (p-1)      (p-1)
carry   carry


So there are at least two carries in this addition, at place values $p^I$ and $p^{I + 1}$.

By Kummer's Theorem, we have:

$p^2 \divides \dbinom {n - m + m} m = \dbinom n m$

Thus the contrapositive is proved.

$\blacksquare$