Exercise 4.1.36* ($\mathrm{lcm}\left \{ \binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}\right\} = \frac{1}{n+1} \, \mathrm{lcm}(1,2,\ldots,n, n+1)$)

Proof.

(a)

We first show the estimation of $\underset{0\le a\le n}{\max <!--\; FUNCTION\; APPLICATION\; -->}{\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{a}\right)$ given by B. Farhi, where $p$ is a prime number.

Let $n=\underset{i=0}{\overset{N}{\sum <!--\; FUNCTION\; APPLICATION\; -->}}{c}_i{p}^i$ be the expansion of $n$ in base $p$, where $N\in \mathbb{N},0\le c_i<p$ (for $i=0,1,\dots ,N$) and $c_N\ne 0$. Then

$$\begin{array}{lll}\hfill \underset{0\le a\le n}{\max <!--\; FUNCTION\; APPLICATION\; -->}{\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{a}\right)={\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{p^N-1}\right)=\{\begin{array}{cc}0\hfill & \text{if }n=p^{N+1}-1,\hfill \\ N-\min <!--\; FUNCTION\; APPLICATION\; -->\{i\in [[0,N]]\mid c_i\ne p-1\}\hfill & \text{otherwise}.\hfill \end{array}& & \hfill \text{(1)}\end{array}$$

• If $n=p^{N+1}-1$, then $c_i=p-1$ for all $i\in [[0,N]]$. Suppose that $0\le a\le N$, and put $b=N-a$. We write $a={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^N{a}_i{p}^i,b={\sum }_{i=0}^N{b}_i{p}^i$ the expansions of $a,b$ in base $p$ (here we don’t suppose that $a_N\ne 0,b_N\ne 0$).

  Let $r_i$ be the carry added to $a_i$ and $b_i$, so that the $r_i$ are defined by

  $$\begin{array}{lll}\hfill \{\begin{array}{cc}{r}_0\hfill & =0\hfill \\ r_{i+1}\hfill & =\lfloor \frac{a_i+b_i+r_i}{p}\rfloor ,\hfill \\ c_i\hfill & =(a_i+b_i+r_i)-p{r}_{i+1}(=(a_i+b_i+r_i)\mathit{mod}p).\hfill \end{array}& & \hfill \text{(2) }\end{array}$$

  (See the solution of Problem 34).

  We show by induction that $r_i=0$ for all $i\in [[0,N]]$.

  By definition, $r_0=0$.

  Suppose now that $r_i=0$ for some $i<N$. Then, by equations (2),

  $$p-1=c_i=(a_i+b_i)-p{r}_{i+1},$$

  thus $p\mid a_i+b_i+1$, where $0<a_i+b_i+1\le 2p-1$, therefore $a_i+b_i+1=p$, thus $r_{i+1}=\lfloor \frac{a_i+b_i}{p}\rfloor =\lfloor \frac{p-1}{p}\rfloor =0.$

  The induction is done, which proves that all the carries $r_i$ are zero. By Kummer’s Theorem (Problem 34), $\left(\genfrac{}{}{0.0pt}{}{n}{a}\right)\not\equiv 0(\mathit{mod}p)$, thus ${\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{a}\right)=0$ for all $a\in [[0,n]]$. This shows that

  $$\underset{0\le a\le n}{\max <!--\; FUNCTION\; APPLICATION\; -->}{\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{a}\right)={\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{p^N-1}\right)=0\text{ if }n=p^{N+1}-1.$$

• Suppose now that $n\ne p^{N+1}-1$. In this case, at least one of the digits of $n$, in base $p$, is different from $p-1$. So we can define

  $$i_0=\min <!--\; FUNCTION\; APPLICATION\; -->\{i\in [[0,N]]\mid c_i\ne p-1\}.$$

  We have to show that for any $a\in [[0,n]]$,

  $$\begin{array}{lll}\hfill {\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{a}\right)\le N-i_0,& & \hfill \text{(3)}\end{array}$$

  and

  $$\begin{array}{lll}\hfill {\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{p^N-1}\right)=N-i_0.& & \hfill \text{(4)}\end{array}$$

As in the preceding case, we write $a={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^N{a}_i{p}^i$, and $b=n-a={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^N{b}_i{p}^i$. By the definition of $i_0$,

$$c_0=c_1=\cdots =c_{i_0-1}=p-1.$$

We show by induction that $r_i=0$ for all $i\in [[0,i_0]]$.

By definition, $r_0=0$.

Suppose now that $r_i=0$ for some $i<i_0$. Then, by equations (2),

$$p-1=c_i=(a_i+b_i)-p{r}_{i+1},$$

thus $p\mid a_i+b_i+1$, where $0<a_i+b_i+1\le 2p-1$, therefore $a_i+b_i+1=p$, thus $r_{i+1}=\lfloor \frac{a_i+b_i}{p}\rfloor =\lfloor \frac{p-1}{p}\rfloor =0.$

The induction is done, which proves that $r_i=0$ for $i\in \{0,1,\dots ,i_0\}$. We note that $r_{N+1}=0$ since $n<p^{N+1}$. Therefore the only possibly nonzero carries are $r_{i_0+1},\dots ,r_N$, so the number of nonzero carries is at most $N-i_0$. The Kummer’s Theorem (Problem 34) shows that the inequalities (3) are true.

Now consider the special case $a=p^N-1={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=0}^{N-1}(p-1)p^i$. The following array summarizes the digits of $a,b,n$:

$i$	$N$	$N-1$	$\text{…}$	$i_0+1$	$i_0$	$i_0-1$	$\text{…}$	$0$
$c_i$	$c_N\ne 0$				$c_{i_0}<p-1$	$p-1$	$\text{…}$	$p-1$
$a_i$	$0$	$p-1$	$\text{…}$	$p-1$	$p-1$	$p-1$	$\text{…}$	$p-1$
$b_i$	$b_N$				$b_{i_0}\ge 1$	$0$	$\text{…}$	$0$
$r_i$	$1$	$1$	$\text{…}$	$1$	$0$	$0$	$\text{…}$	$0$

For $0\le i<i_0$, $c_i=a_i=p-1$ , thus $b_i=0$ and $r_i=0$. But $c_{i_0}<p-1$, therefore $b_{i_0}\ne 0$, so $a_{i_0}+b_{i_0}\ge p$, which gives $r_{i_0+1}=1$. If we suppose that $r_i=1$ for some $i$, $i_0+1\le i<N$, then $a_i+b_i+r_i=(p-1)+b_i+1\ge p$, thus $r_{i+1}=1$. This induction shows that

$$r_{i_0}+1=\cdots =r_N=1,$$

and $r_{N+1}=0$ since $n<p^{K+1}$.

So there are exactly $N-i_0$ nonzero carries when we add $a$ and $b$ in base $p$. According to Kummer’s Theorem (Problem 34),

$$\begin{array}{lll}\hfill {\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{p^N-1}\right)=N-i_0,& & \hfill \end{array}$$

so the equality (4) is proven. By (3) and (4),

$$\begin{array}{lll}\hfill \underset{0\le a\le n}{\max <!--\; FUNCTION\; APPLICATION\; -->}{\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{a}\right)={\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{p^N-1}\right)=N-\min <!--\; FUNCTION\; APPLICATION\; -->\{i\in [[0,N]]\mid c_i\ne p-1\}\text{ if }n\ne p^{N+1}-1.& & \hfill \text{(5)}\end{array}$$

The equality (1) is proven in both cases.

(b)

Now we can prove the main result: for all $n\in \mathbb{N}$, $$\begin{array}{lll}\hfill \mathrm{lcm}\left\{\left(\genfrac{}{}{0.0pt}{}{n}{0}\right),\left(\genfrac{}{}{0.0pt}{}{n}{1}\right),\dots ,\left(\genfrac{}{}{0.0pt}{}{n}{n}\right)\right\}=\frac{1}{n+1}\mathrm{lcm}(1,2,\dots ,n,n+1).& & \hfill \text{(6)}\end{array}$$

(we add $\left(\genfrac{}{}{0.0pt}{}{n}{0}\right)=1$ to the list, so the property remains true if $n=0$.)

To prove (6), we show that for all prime numbers $p$,

$$\begin{array}{lll}\hfill {\nu }_p\left(\mathrm{lcm}\left\{\left(\genfrac{}{}{0.0pt}{}{n}{0}\right),\left(\genfrac{}{}{0.0pt}{}{n}{1}\right),\dots ,\left(\genfrac{}{}{0.0pt}{}{n}{n}\right)\right\}\right)={\nu }_p\left(\frac{1}{n+1}\mathrm{lcm}(1,2,\dots ,n,n+1)\right).& & \hfill \text{(7) }\end{array}$$

Since ${\nu }_p\left(\mathrm{lcm}\left\{\left(\genfrac{}{}{0.0pt}{}{n}{0}\right),\left(\genfrac{}{}{0.0pt}{}{n}{1}\right),\dots ,\left(\genfrac{}{}{0.0pt}{}{n}{n}\right)\right\}\right)=\underset{0\le a\le n}{\max <!--\; FUNCTION\; APPLICATION\; -->}{\nu }_p\left(\genfrac{}{}{0.0pt}{}{n}{a}\right)$, we know the left member by part (a):

$$\begin{array}{lll}\hfill {\nu }_p\left(\mathrm{lcm}\left\{\left(\genfrac{}{}{0.0pt}{}{n}{0}\right),\left(\genfrac{}{}{0.0pt}{}{n}{1}\right),\dots ,\left(\genfrac{}{}{0.0pt}{}{n}{n}\right)\right\}\right)=\{\begin{array}{cc}0\hfill & \text{if }n=p^{N+1}-1,\hfill \\ N-\min <!--\; FUNCTION\; APPLICATION\; -->\{i\in [[0,N]]\mid c_i\ne p-1\}\hfill & \text{otherwise}.\hfill \end{array}& & \hfill \text{(8)}\end{array}$$

Next

$${\nu }_p(\mathrm{lcm}(1,2,\dots ,n,n+1))=\underset{1\le k\le n+1}{\max <!--\; FUNCTION\; APPLICATION\; -->}({\nu }_p(k)).$$

• Suppose first that $n\ne p^{N+1}-1$. If $1\le k\le n+1$, then $k<p^{N+1}$. Therefore ${\nu }_p(k)\le N$. Moreover, for $k=p^N$, ${\nu }_p(k)=N$. This shows that $\underset{1\le k\le n+1}{\max <!--\; FUNCTION\; APPLICATION\; -->}({\nu }_p(k))=N$, so

  $${\nu }_p(\mathrm{lcm}(1,2,\dots ,n,n+1))=N(n\ne p^{N+1}-1).$$

• We suppose next that $n=p^{N+1}-1$. Then ${\nu }_p(n+1)=N+1$, and for every $k\in [[1,n]]$, ${\nu }_p(k)\le N$, thus $\underset{1\le k\le n+1}{\max <!--\; FUNCTION\; APPLICATION\; -->}({\nu }_p(k))=N+1$, so

  $${\nu }_p(\mathrm{lcm}(1,2,\dots ,n,n+1)=N+1(n=p^{N+1}-1).$$

We have proved

$$\begin{array}{lll}\hfill {\nu }_p(\mathrm{lcm}(1,2,\dots ,n,n+1))=\{\begin{array}{cc}N+1\hfill & \text{if }n=p^{N+1}-1,\hfill \\ N\hfill & \text{otherwise.}\hfill \end{array}& & \hfill \text{(9)}\end{array}$$

It remains to estimate ${\nu }_p(n+1)$. If $n=p^{N+1}-1$, then $n+1=p^{N+1}$, so ${\nu }_p(n+1)=N+1$. Otherwise, there is some digit $c_i$ of $n$ such that $c_i\ne p-1$. As in part (a), put

$$i_0=\min <!--\; FUNCTION\; APPLICATION\; -->\{i\in [[0,N]]\mid c_i\ne p-1\}.$$

Then

$$\begin{array}{llll}\hfill n+1& =\underset{i=0}{\overset{N}{\sum }}{c}_i{p}^i+1& \hfill & \\ \hfill & =\underset{i=i_0}{\overset{N}{\sum }}{c}_i{p}^i+\underset{i=0}{\overset{i_0-1}{\sum }}(p-1)p^i+1& \hfill & \\ \hfill & =\underset{i=i_0}{\overset{N}{\sum }}{c}_i{p}^i+p^{i_0}& \hfill & \\ \hfill & =p^{i_0}\left(\underset{i=i_0+1}{\overset{N}{\sum }}{c}_i{p}^{i-i_0}+c_{i_0}+1\right).& \hfill & \end{array}$$

Here $p\mid {\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=i_0+1}^N{c}_i{p}^{i-i_0}$, but $1\le c_{i_0}+1<2p$ and $c_{i_0}+1\ne p$, thus $p\nmid c_{i_0}+1$. Therefore $p\nmid {\sum <!--\; FUNCTION\; APPLICATION\; -->}_{i=i_0+1}^N{c}_i{p}^{i-i_0}+c_{i_0}+1$. This shows that ${\nu }_p(n+1)=i_0$.

To summarize,

$$\begin{array}{lll}\hfill {\nu }_p(n+1)=\{\begin{array}{cc}N+1\hfill & \text{if }n=p^{N+1}-1,\hfill \\ \min <!--\; FUNCTION\; APPLICATION\; -->\{i\in [[0,N]]\mid c_i\ne p-1\}\hfill & \text{otherwise}.\hfill \end{array}& & \hfill \text{(10)}\end{array}$$

Since ${\nu }_p(a∕b)={\nu }_p(a)-{\nu }_p(b)$ for all positive integers $a,b$, the equalities (9) and (10) give

$$\begin{array}{lll}\hfill {\nu }_p\left(\frac{1}{n+1}\mathrm{lcm}(1,2,\dots ,n,n+1)\right)=\{\begin{array}{cc}0\hfill & \text{if }n=p^{N+1}-1,\hfill \\ N-\min <!--\; FUNCTION\; APPLICATION\; -->\{i\in [[0,N]]\mid c_i\ne p-1\}\hfill & \text{otherwise.}\hfill \end{array}& & \hfill \text{(11)}\end{array}$$

The comparison of (8) and (11) give (7), so (6) is true: for all $n\in \mathbb{N}$,

$$\begin{array}{lll}\hfill \mathrm{lcm}\left\{\left(\genfrac{}{}{0.0pt}{}{n}{0}\right),\left(\genfrac{}{}{0.0pt}{}{n}{1}\right),\dots ,\left(\genfrac{}{}{0.0pt}{}{n}{n}\right)\right\}=\frac{1}{n+1}\mathrm{lcm}(1,2,\dots ,n,n+1).& & \hfill \end{array}$$