I was playing around with pascal triangle I noticed an interesting property concerning the greatest common divisor $gcd$ of binomial coefficients along a vertical line. Specifically, the line containing $2$ is the only one where the $\gcd$ of all coefficients is greater than $1$ (namely, $2$).
This made me wonder:
What $n \in \mathbb{N}$ such that $\gcd _{k\ge1 }\left\{\binom{n+2k-2}{k}\right\}>1$
I tried every number between $2 $ and $10$ by hand which all failed that made me conjecture that $n=2$ is the only number which has $\gcd _{k\ge1 }\left\{\binom{n+2k-2}{k}\right\}>1$
I wrote a simple python code to test that $2$ is the only number that has this property
for n in range(2,20_001):
a=n
for k in range (2,10_001):
math.gcd(a, math.comb(n+2*k-2,k))
if math.gcd(a, math.comb(n+2*k-2,k))==1:
break
a=math.gcd(a, math.comb(n+2*k-2,k))
if k==10_000:
print(n)
print(a)
print("\n")
between $2$ and $20,000$ the only number which has this property is 2.
Another interesting thing about this sequence for $n\ne 2$ $\gcd _{1 \le k\le m}\left\{\binom{n+2k-2}{k}\right\}>1$ fail at a power of $2$, in other words the for $ n \ne 2$ $\gcd _{1 \le k\le m}\left\{\binom{n+2k-2}{k}\right\}>1$ will first be broken when $m$ is a power of $2$.
Here is the first 100 $n$ and the first $m$ that $\gcd _{1 \le k\le m}\left\{\binom{n+2k-2}{k}\right\}=1$ in the form "(n,m)"
(3,2),
(4,2),
(5,2),
(6,4),
(7,2),
(8,2),
(9,2),
(10,8),
(11,2),
(12,2),
(13,2),
(14,4),
(15,2),
(16,2),
(17,2),
(18,16),
(19,2),
(20,2),
(21,2),
(22,4),
(23,2),
(24,2),
(25,2),
(26,8),
(27,2),
(28,2),
(29,2),
(30,4),
(31,2),
(32,2),
(33,2),
(34,32),
(35,2),
(36,2),
(37,2),
(38,4),
(39,2),
(40,2),
(41,2),
(42,8),
(43,2),
(44,2),
(45,2),
(46,4),
(47,2),
(48,2),
(49,2),
(50,16),
(51,2),
(52,2),
(53,2),
(54,4),
(55,2),
(56,2),
(57,2),
(58,8),
(59,2),
(60,2),
(61,2),
(62,4),
(63,2),
(64,2),
(65,2),
(66,64),
(67,2),
(68,2),
(69,2),
(70,4),
(71,2),
(72,2),
(73,2),
(74,8),
(75,2),
(76,2),
(77,2),
(78,4),
(79,2),
(80,2),
(81,2),
(82,16),
(83,2),
(84,2),
(85,2),
(86,4),
(87,2),
(88,2),
(89,2),
(90,8),
(91,2),
(92,2),
(93,2),
(94,4),
(95,2),
(96,2),
(97,2),
(98,32),
(99,2),
(100,2),
This sequence is also interesting because of its pattern i.e Three $2$s followed by a power of $2$ greater than $2$.
My questions are:
- How to prove that $n=2$ is the only $n \in \mathbb{N}$ such that $\gcd _{k\ge1 }\left\{\binom{n+2k-2}{k}\right\}>1$
- For $n \ne 2$ how to prove that the first $m \in \mathbb{N}$ such that $\gcd _{1 \le k\le m}\left\{\binom{n+2k-2}{k}\right\}=1$ is always a power of $2$
- What is the pattern for such $m$?
With the help of @ronno observation I was able to write a code that checked for all $n \le 10^6$ and none of them had a gcd >1 except 2
Best Answer
Let $n\geq2$ be a positive integer, and consider the sequence $(a_k)_{k\geq1}$ defined by $a_k:=\tbinom{n+2k-2}{k}$. You want to find the least positive integer $m$ such that $$\gcd(a_1,\ldots,a_m)=1.$$ The first two terms of the sequence are $a_1=\tbinom{n}{1}=n$ and $a_2=\tbinom{n+2}{2}=\tfrac12(n+2)(n+1)$, and so $$\gcd(a_1,2a_2)=\gcd(n,2),$$ which already shows that $\gcd(a_1,\ldots,a_k)$ divides $2$ for all $k\geq2$, and in particular, that $m=2$ if $n$ is odd. For even $n$ we see that $m$ is the smallest positive integer such that $a_m$ is odd.
By Lucas' theorem the binomial coefficient $\binom{a}{b}$ is odd if and only if the nonzero digits in the binary expansion of $b$ are also nonzero in the binary expansion of $a$. Then by induction we find that the least $k$ for which $\tbinom{(n-2)+2k}{k}$ is odd is the largest power of $2$ dividing $n-2$.