Prove or disprove: For any positive integer $k$ there exists an integer $n > 1$ such that the binomial coeffcient $\binom{n}{i}$ is divisible by $k$ for any $1 \leq i \leq n-1.$
Problem
Source: 11-th Hungary-Israel Binational Mathematical Competition 2000
Tags: algebra, binomial theorem, number theory unsolved, number theory
21.04.2007 03:14
The statement is false. The case $k = 4$ is a counterexample. If $n$ is a power of 2, then set $i = n / 2$. Then we can show that $\binom{n}{i}$ is not a multiple of $4$. One method is to use Kummer's theorem. Otherwise, suppose that when $n$ is written in binary (base 2), it has a 1 in the $j$th position from the right. Then set $i = 2^{j}$. This time, we can show that $\binom{n}{i}$ is odd, and so not a multiple of 4. Again, we can use Kummer's theorem. (There is a typo in the linked page: Where it says add $n$ and $n-m$, it means add $m$ and $n-m$.)
22.04.2007 16:37
for $k=4$ if $n$ is a power of $2$, $i=\frac{n}{2}$ if for some $k$, $2^{k}<n<2^{k+1}$, $i=2^{k}$ doesn't work.
22.04.2007 17:16
It is false if k is not square free ($k\not =rad(k)$). If $k=rad(k)$ work $n=k^{2}$.
23.04.2007 18:32
Here's another approach to show that $k = 4$ is a counterexample. By the Binomial Theorem, we have \[\sum_{i = 1}^{n-1}\binom{n}{i}= 2^{n}-2. \] For $n > 1$, the right-hand side is not divisible by 4. Hence one of the individual terms $\binom{n}{i}$ is not divisible by 4.
23.04.2007 21:17
to Ravi. Read my post. If $k\not = rad(k)$ it is false.
24.04.2007 04:46
Yes, I read your post, and agree with what it says. But since I didn't see a proof there, I thought I would write a simple proof for the case $k = 4$. You are welcome to write a proof for the general case.
24.04.2007 08:18
Obviosly $k|n=C_{n}^{1}.$ If $4|k$ work Ravi's proof. Let $p^{2}|k$ p-odd prime. If $n=p^{k}$ we get \[C_{p^{k}}^{p^{k-1}}=p(mod \ p^{2}).\] If $n=p^{k}m, p\not |p$, then $p\not | C_{n}^{p^{k}}$. It proof, that $k=rad(k)=p_{1}...p_{m}$, were $p_{i}$ distinct prime divisors. If $m>1$ we get $p_{1}\not |C_{n}^{p_{1}}$. Therefore $k=p$ prime number and $n=p^{k},k\in N$.
25.04.2007 12:15
This also follows very easy from here: http://www.mathlinks.ro/Forum/viewtopic.php?t=133601