- #1

- 3

- 0

## Homework Statement

Is it true that for each ##n\geq 2## there are two primes ##p, q \neq 1## that divide every ##\binom{n}{k}## for ##1\leq k\leq n-1##?

Examples:

For ##n=6: \binom{6}{1}=6; \binom{6}{2}=15; \binom{6}{3}=20; \binom{6}{4}=15; \binom{6}{5}=6.## So we can have ##p=2## and ##q=3##.

For ##n=3: \binom{3}{1}=3; \binom{3}{2}=3.## So we can have ##p=3## and ##q=17## (or any other prime). We just have to show that each ##\binom{n}{k}## is divisible by at most two primes.

## Homework Equations

##\binom{n}{k}=\frac{n!}{k!(n-k)!}##

## The Attempt at a Solution

Proof by induction:

Base case: True for ##2, 3##

Induction on ##n##: Assume true for ##n##. Prove for ##n+1##:

$$\binom{n+1}{k}=\frac{(n+1)!}{k!(n-k+1)!}=\frac{n+1}{n-k+1}*\frac{n!}{k!(n-k)!}$$

Now what? Is it possible to say that since ##\frac{n!}{k!(n-k)!}## is divisible by primes (by assumption) that somehow ##\frac{n+1}{n-k+1}*\frac{n!}{k!(n-k)!}## is as well?