Exercise 4.1.26* (Gcd of $\binom{n}{j},\ 1 \leq j \leq n-1$)

Question

Let $d$ be the greatest common divisor of the coefficients of $(x+y)^n$ except the first and last, where $n$ is any positive integer $>1$. Prove that $d = p$ if $n$ is a power of a prime $p$, and that $d = 1$ otherwise.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}} ewcommand{\N}{\mathbb{N}} \begin{proof} Suppose that $n$ is a power of a prime $p$. So $n = p^k$ for some exponent $k \geq 1$. By Problem 2.1.45 we know that $$\binom{n}{j} = \binom{p^k}{j} \equiv 0 \pmod p \qquad (1 \leq j \leq n-1).$$ Therefore $p \mid d$, where $d$ is the greater common divisor $$d =\bigwedge\limits_{1 \leq j \leq n-1} \binom{n}{j} = \binom{n}{1} \wedge \binom{n}{2} \wedge \cdots \wedge \binom{n}{n-1}$$ of the coefficients of $(x+y)^n$ except the first and last. We note that $d \mid \binom{n}{1} = n = p^k$, thus $d = p^i$ is a power of $p$, and $i \geq 1$ since $p \mid d$. Moreover, by Theorem 4.2 (de Polignac's formula), \begin{align} u_p \binom{p^k}{p^{k-1}} &= \sum_{i=1}^\infty \left \lfloor \frac{p^k}{p^i} ight floor - \sum_{i=1}^\infty \left \lfloor \frac{p^{k-1}}{p^i} ight floor - \sum_{i=1}^\infty \left \lfloor \frac{p^k - p^{k-1}}{p^i} ight floor, \end{align} where \begin{align*} \sum_{i=1}^\infty \left \lfloor \frac{p^k}{p^i} ight floor&= p^{k-1} + p^{k-2} + \cdots + 1 = \frac{p^k-1}{p-1},\ \sum_{i=1}^\infty \left \lfloor \frac{p^{k-1}}{p^i} ight floor&= p^{k-2} + p^{k-3} + \cdots + 1 = \frac{p^{k-2}-1}{p-1},\ \sum_{i=1}^\infty \left \lfloor \frac{p^k - p^{k-1}}{p^i} ight floor&= \sum_{i=1}^{k-1} p^{k-1-i}(p-1) & (p^{k-1-i}(p-1) <1 ext{ if } i \geq k)\ &=(p-1)(p^{k-2} + p^{k-3} + \cdots + 1)\ &= (p-1)\, \frac{p^{k-1} - 1}{p-1}\ &= \frac{p^k - p^{k-1} - p + 1}{p-1}. \end{align*} By equation (1), \begin{align*} u_p \binom{p^k}{p^{k-1}} &=\frac{1}{p-1} \left( p^k - 1 - p^{k-1} + 1 - p^k + p^{k-1} + p - 1 ight)\ &=\frac{1}{p-1} (p-1)\ &= 1. \end{align*} Therefore $ u_p \binom{p^k}{p^{k-1}} =\lambda p$, where $\lambda \wedge p = 1$. Here $d = p^i \mid \lambda p$, where $i \geq 1$, thus $p^{i-1} \mid \lambda$, where $p mid \lambda$, so $i = 1$ and $d = p$. If $n>1$ is a power of $p$, then $$d =\bigwedge\limits_{1 \leq j \leq n-1} \binom{n}{j} = p.$$ \bigskip Suppose now that $n$ is not a power of a prime, so that $n = p_1^{a_1} p_2^{a_2}\cdots p_l^{a_l}$ is the decomposition of $n$ in prime factors, with $l \geq 2$. Put $p = p_i$ any prime factor of $n$, and $a = a_i$. Then $n = p^a w$, where $p mid w$. We show that $$ u_p \binom{p^a w}{p^a} = 0,\qquad (p mid w).$$ (The condition $p mid w$ is necessary: for instance $ 5 \mid \binom {5 \cdot 5}{5}$.) Since $$\binom{p^a w}{p^a} = \frac{p^a w (p^a w - 1) \cdots (p^a w - p^a + 1)}{p^a (p^a - 1) \cdots 1} = \prod_{i=0}^{p^a-1} \frac{p^aw - i}{p^a -i},$$ we obtain \begin{align} u_p \binom{p^a w}{p^a} &= \sum_{i=0}^{p^a - 1} ( u_p (p^a w - i) - u_p(p^a - i)) \end{align} We compare $ u_p (p^a w - i) $ and $ u_p(p^a - i)$ for $0 \leq i < p^a$. \begin{itemize} \item If $i = 0$, since $p mid w$, $ u_p(p^a w) = u_p(p^a) = a$. \item If $1 \leq i < p^a$, we write $i = p^b \lambda$, where $0 \leq b < a$. Then \begin{align*} p^a w - i &= p^a w - p^b \lambda\ &= p^b( p^{a-b} - \lambda)\ &= p^b \mu, \end{align*} where $\mu = p^{a-b} - \lambda$ is prime to $p$: since $a-b >0$, if $p \mid \mu$, then $p \mid \lambda$, which is false by definition of $\lambda$. Therefore $$ u_p( p^a w - i ) = b,$$ and similarly, with $w = 1$, $$ u_p(p^a - i) = b = u_p(p^a w -i).$$ \end{itemize} Then $ u_p( p^a w - i ) = u_p(p^a - i) $ for all $i \in [\![0, p^a[\![$. Then the equation (2) gives \begin{align} u_p \binom{p^a w}{p^a} &=0 \qquad ( ext{ if }p mid w). \end{align} We note that $d \mid n = \binom{n}{1}$, thus $d = p_1^{b_1} \cdots p_l^{b_l}$, where $b_i \geq 0$. By equation (3), $$p_i mid \binom{n}{p_i^{a_i}} ext{ for }i=1, \ldots,l.$$ This shows that $p_i mid d$ for every index $i$, so $b_1 = b_2 =\cdots = b_l = 0$, and $d = 1$. If $n>1$ is not a power of a prime, then $$d =\bigwedge\limits_{1 \leq j \leq n-1} \binom{n}{j} = 1.$$ \end{proof}

Exercise 4.1.26* (Gcd of $\binom{n}{j},\ 1 \leq j \leq n-1$)

Answers

Comments

Exercise 4.1.26* (Gcd of $\binom{n}{j},\ 1 \leq j \leq n-1$)

Answers

Comments

Add answer