GCD of binomial coefficients

1.4k Views Asked by At

Can the following be proved or disproved?

$$\gcd\left(\binom{n}{1} , \binom{n}{2} , \binom{n}{3},...........,\binom{n}{\lfloor \frac n2 \rfloor}\right)$$

Where $n \ge 4$ and is a positive integer

Is always a prime number or 1.

It would be very helpful if the way to prove or disprove it may make use of the properties of Pascal's triangle.

2

There are 2 best solutions below

0
On BEST ANSWER

$\newcommand{\Z}{\mathbb{Z}}$Suppose $n$ is not a prime-power, and let $$n = \prod_{i=1}^{k} p_{i}^{e_{i}}$$ with $p_{i}$ distinct primes, $e_{i} > 0$ for each $i$.

Write $$n_{j} = \prod_{i \ne j} p_{i}^{e_{i}}.$$

Then it is well known that $$ \binom{n}{p_{i}^{e_{i}}} \equiv \binom{p_{i}^{e_{i}} n_{i}}{p_{i}^{e_{i}}} \equiv n_{i} \pmod{p}, $$ so that $\dbinom{n}{p_{i}^{e_{i}}}$ is not divisible by $p_{i}$. Since your gcd is a divisor of $n = \dbinom{n}{1}$, this shows that the gcd is $1$ in this case.

If $n = p^{e}$ is a power of the prime $p$, then the equation in $\Z/p\Z[x]$ $$ (1 + x)^{p^{e}} = 1 + x^{p^{e}} $$ shows that all of your binomial coefficients are divisible by $p$, and their gcd divides $p^e = \dbinom{p^e} {1}$.

But by Kummer, the highest power of $p$ dividing $$ \binom{p^{e}}{p^{e-1}} $$ is $p$, as there is precisely one carry in the $p$-adic addition of $p^{e-1}$ and $p^{e} - p^{e-1} = (p-1) p^{e-1}$, so that your gcd is $p$.

0
On

$hint$

if n is a prime then $n\choose r$ is always a multiple of $n$ because non of factor of denominator can cancel $n$