Brain exercising #1

I happened to see this problem on Twitter. It reminded me of my secondary school when I was passionate about solving math problems :)... I am thinking of a little corner of this blog for this sort of exercising.

Claim: If $p$ is prime, all the coefficients in $(a+b)^p$ except the first and the last are divisible by $p$.

If p is prime, all the coefficients in (a+b)^p except the first and last are divisible by p.

— Algebra Fact (@AlgebraFact) August 29, 2017

Equivalent claim: If $p$ is prime, $p \mid C^k\_p$ for all $k, 0<k<p$.

Proof.

$C^k\_p = \frac{p!}{k! (p-k)!} = \frac{p(p-1)!}{k! (p-k)!}$

Let $x = (p-1)!, y = k!(p-k)!$. Then $C^k\_p = \frac{px}{y}$

$C^k\_p \in \mathbb{Z} \implies y \mid px \hspace{5pt} (*)$

We know that $\forall z<p: gcd(p, z) = 1$. So, $\forall z<p: gcd(p, z!) = 1$.

Because $k, p-k < p$, we have $gcd(p, k!) = gcd(p, (p-k)!) = 1$

$\implies gcd(p, y) = 1 \hspace{5pt} (**)$

From $(*)$, $(**)$ $\implies y \mid x \implies p \mid p \;\frac{x}{y} = C^k\_p$ ■