Binomial Congruence

Number Theory Level 4

Consider the following binomial coefficient: $\dbinom{n}{\big\lceil\frac{n}{2}\big\rceil},$ where $\lceil \cdot \rceil$ is the ceiling function.

If it is divisible by $n$ , what can be said about $n \geq 2$ ?

(1) Only prime odd integers work.
(2) None of the even composite integers work.
(3) All odd integers work.

Statement (2) Statement (1) Statement (3)

1 solution

Chaebum Sheen
Dec 5, 2016

Note that when $x=2k+1$ , $\binom{2k+1}{k+1}=\frac{2k+1}{k+1} \binom {2k}{k} = (2k+1) \times \frac{1}{k+1} \binom {2k}{k}$

Since $\gcd(2k+1, k+1)=\gcd(1, k+1)=1$ , we can conclude that $\binom{2k+1}{k+1} \equiv 0 \pmod {2k+1}$

Statement $\text{(2)}$ is incorrect because $n=12$ works. Statement $\text{(1)}$ is incorrect because all odd integers work as well.

Actually 2 isn't composite, so it doesn't show that statement 2 doesn't work. However 12 does...

Geoff Pilling - 4 years, 6 months ago

Thank you, I have fixed the answer.

Chaebum Sheen - 4 years, 6 months ago

For completeness, you should show that $\frac{1}{k+1} \binom {2k}{k}$ is an integer. For example by mentioning the catalan numbers

Julian Poon - 4 years, 6 months ago

Shouldn't that be unnecessary? If $2k+1=a, k+1=b, \binom{2k}{k}=c$ , I have shown that $\gcd(a,b)=1$ and that $\frac{ac}{b}$ is an integer. Since $a$ and $b$ are coprime, this implies that $b|c$ . So, one can see from what I have written already that $\frac{1}{k+1} \binom{2k}{k} \in \mathbb{N}$

Chaebum Sheen - 4 years, 6 months ago

Ah yes, I've missed that

Julian Poon - 4 years, 6 months ago

You mean "statements", not "students". :)

Good solution!

Michael Huang - 4 years, 6 months ago

Thank you, I have fixed the answer.

Chaebum Sheen - 4 years, 6 months ago

Binomial Congruence

1 solution

0 pending reports