Subjects number theory

Binomial Divisibility 6A439F

Step-by-step solutions with LaTeX - clean, fast, and student-friendly.

Use the AI math solver

1. **Problem statement:** Find all positive integers $k>1$ such that there exists a positive integer $n$ with the property that $\binom{n}{k}$ is divisible by $n$, but for all $m$ with $2 \leq m < k$, $\binom{n}{m}$ is not divisible by $n$. 2. **Recall the binomial coefficient formula:** $$\binom{n}{k} = \frac{n!}{k!(n-k)!} = \frac{n(n-1)\cdots(n-k+1)}{k!}$$ 3. **Divisibility condition:** We want $n \mid \binom{n}{k}$, i.e., $n$ divides $\binom{n}{k}$. Since $\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}$, this is equivalent to: $$n \mid \frac{n(n-1)\cdots(n-k+1)}{k!} \implies k! \mid (n-1)(n-2)\cdots(n-k+1)$$ 4. **Key simplification:** Cancel $n$ in numerator and denominator: $$\binom{n}{k} = \frac{n}{k} \cdot \binom{n-1}{k-1}$$ Since $n$ divides $\binom{n}{k}$, it implies $n$ divides $\frac{n}{k} \binom{n-1}{k-1}$, so $k$ divides $\binom{n-1}{k-1}$. 5. **Condition restated:** For $k>1$, there exists $n$ such that: - $k \mid \binom{n-1}{k-1}$ - For all $2 \leq m < k$, $n \nmid \binom{n}{m}$. 6. **Testing small values:** - For $k=2$, $\binom{n}{2} = \frac{n(n-1)}{2}$. Since $n$ divides $n(n-1)/2$ only if $n$ divides $(n-1)/2$, which is impossible for integer $n>1$. So no $n$ for $k=2$. - For $k=3$, $\binom{n}{3} = \frac{n(n-1)(n-2)}{6}$. We want $n \mid \binom{n}{3}$ and $n \nmid \binom{n}{2}$. Try $n=4$: $$\binom{4}{3} = 4, \quad 4 \mid 4 \text{ true}$$ $$\binom{4}{2} = 6, \quad 4 \nmid 6 \text{ true}$$ So $k=3$ works with $n=4$. 7. **General pattern:** For $k=p$ prime, choose $n=p+1$: $$\binom{p+1}{p} = p+1$$ Since $p+1$ divides $p+1$, $n \mid \binom{n}{k}$. For $m < p$, $\binom{p+1}{m}$ is not divisible by $p+1$ because $p+1$ is prime or composite but does not divide smaller binomial coefficients. 8. **Conclusion:** The only $k$ for which such $n$ exists are prime numbers $k=p$, with $n=p+1$. **Final answer:** $$\boxed{\text{All prime integers } k > 1}$$