1. ## Binomial Coefficient

For a prime $\displaystyle \displaystyle p$, show $\displaystyle \displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \bmod{p^2}$.

2. I try not to consider the fact $\displaystyle \binom{n}{k} = \frac{ n!}{ k! (n-k)! }$ , i just regard it as the coefficient of a term in $\displaystyle (1+x)^n$

We know $\displaystyle \binom{ap}{bp}$ is the coefficient of $\displaystyle x^{bp}$ in the expansion of $\displaystyle (1+x)^{ap}$ while $\displaystyle \binom{a}{b}$ is the coefficient of $\displaystyle x^{bp}$ in the expansion of $\displaystyle (1+x^p)^a$ . Therefore , $\displaystyle \binom{ap}{bp} - \binom{a}{b}$ is the coefficient of $\displaystyle x^{bp}$ of $\displaystyle (1+x)^{ap} - (1+x^p)^a$ .

I would like to show that all the terms that the degrees are the multiple of prime $\displaystyle p$ are congruent to zero modulo $\displaystyle p^2$ .

I consider $\displaystyle (1+x)^{ap} - (1+x^p)^a = [ (1+x)^p ]^a - [(1+x^p)]^a$

$\displaystyle = [(1+x)^p - 1 - x^p ] [ (1+x)^{p(a-1)} + (1+x)^{p(a-2)} ( 1 + x^p) + ... + (1+x)^p ( 1 + x^p)^{a-2} + (1+x^p)^{a-1} ]$

Note that all the terms in $\displaystyle (1+x)^p - 1 - x^p$ are divisible by $\displaystyle p$ .

Then i consider the second polynomial , the annoying one .

$\displaystyle P(x) = (1+x)^{p(a-1)} + (1+x)^{p(a-2)} ( 1 + x^p) + ... + (1+x)^p ( 1 + x^p)^{a-2} + (1+x^p)^{a-1}$

I use the fact $\displaystyle (1+x)^p \equiv 1+ x^p \bmod{p}$ to simplify $\displaystyle P(x)$ :

$\displaystyle P(x) = (1+x^p)^{a-1} + (1+x^p)^{a-2} ( 1+ x^p ) + ... (1+x^p)(1+x^p)^{a-2} + (1+x^p)^{a-1} + p F(x)$

$\displaystyle = a ( 1+ x^p )^{a-1} + p F(x)$

Then we are done , haha , let's get back the first polynomial $\displaystyle (1+x)^p - 1 - x^p = \binom{p}{1}x + \binom{p}{2} x^2 + ... + \binom{p}{p-1} x^{p-1}$ whose degree ranges from $\displaystyle 1$ to $\displaystyle p-1$ so they are prime to $\displaystyle p$ . Consider $\displaystyle a(1+x^p)^{a-1}$ , we find that the degrees are all mutiple of $\displaystyle p$ so they become useless in the expansion if we are evaluating the coefficient of $\displaystyle x^{bp}$ since no terms in $\displaystyle (1+x)^p - 1 - x^p$ could make the 'connection' to them . Therefore , the coefficient we are considering ( of $\displaystyle x^{bp}$ ) is necessarily the mutiple of $\displaystyle p^2$ , one $\displaystyle p$ from $\displaystyle (1+x)^p - 1 - x^p$ and one from $\displaystyle p F(x)$ .

Remarks :

I don't like this result ... i am going to show that

For a prime $\displaystyle p \geq 5$ we always have

$\displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \bmod{p^3}$ :

Let's check my solution , write $\displaystyle A = (1+x)^p - 1 - x^p$ or $\displaystyle (1+x)^p = 1 + x^p + A$

$\displaystyle P(x) \equiv [ ( 1+ x^p )^{a-1} + (1+x^p)^{a-2} (a-1) A] + [ ( 1+ x^p )^{a-1} + (1+x^p)^{a-2} (a-2) A ] +$ $\displaystyle ... + [( 1+ x^p )^{a-1} + (1+x^p)^{a-2} A ] + (1+x^p)^{a-1} \bmod{p^2}$

$\displaystyle \equiv a(1+x^p)^{a-1} + A(1+x^p)^{a-2} ~ [ 1+ 2+3+...+ (a-1) ] \bmod{p^2}$

$\displaystyle \equiv a(1+x^p)^{a-1} + [(1+x)^p - 1 - x^p ] (1+x^p)^{a-2} \cdot \frac{a(a-1)}{2} \bmod{p^2} ~~~~ a > 1$

Then the coefficient of $\displaystyle x^{bp}$ in $\displaystyle P(x)$ is congruent to ($\displaystyle \bmod{p^3}$ ) that in $\displaystyle [(1+x)^p - 1 - x^p ]^2 (1+x^p)^{a-2} \cdot \frac{a(a-1)}{2}$ . It suffices to show that the coefficient of $\displaystyle x^{p}$ in $\displaystyle [(1+x)^p - 1 - x^p ]^2$ is congruent to zero modulo $\displaystyle p^3$ .

ie :

$\displaystyle \binom{p}{1}^2 + \binom{p}{2}^2 + ... + \binom{p}{p-1}^2 = \binom{2p}{p} - 2 \equiv 0 \bmod{p^3}$ .

Please see this post , http://www.mathhelpforum.com/math-he...nt-149645.html
It is not a help begging but a challenge , let's finish the proof by solving my challenge .

3. let $\displaystyle f(x)=\prod_{k=1}^{p-1}(x-k)=x^{p-1}-a_1x^{p-2} + \cdots -a_{p-2}x + a_{p-1}.$ by the Fermat's little theorem, in $\displaystyle (\mathbb{Z}/p\mathbb{Z})[x],$ we have $\displaystyle f(x)=x^{p-1}-1.$

as a result $\displaystyle (p-1)!=a_{p-1} \equiv -1 \mod p,$ which is Wilson's theorem, and $\displaystyle a_j \equiv 0 \mod p,$ for all $\displaystyle j \neq p-1.$ in particular $\displaystyle f(np) \equiv -1 \mod p^2,$ for any integer $\displaystyle n.$

thus $\displaystyle f(ap)f((a-1)p) \cdots f((a-b+1)p) \equiv (-1)^b \mod p^2$ and $\displaystyle f(bp)f((b-1)p) \cdots f(p) \equiv (-1)^b \mod p^2.$ the result now follows from the trivial identity

$\displaystyle \displaystyle \binom{ap}{bp}=\binom{a}{b} \frac{f(ap)f((a-1)p) \cdots f((a-b+1)p)}{f(bp)f((b-1)p) \cdots f(p)}.$

simplependulum's question is also solved by this method and using an old result due to Wolstenholmes which says that for $\displaystyle p>3: \ a_{p-2} \equiv 0 \mod p^2.$

thus $\displaystyle f(np) \equiv -1 \mod p^3$ for all integers $\displaystyle n.$ therefore for all primes $\displaystyle p > 3$ and all integers $\displaystyle a,b$ we have $\displaystyle \displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \mod p^3.$

4. simplependulum's question is also solved by this method and using an old result due to Wolstenholmes which says that for $\displaystyle p>3: \ a_{p-2} \equiv 0 \mod p^2.$

thus $\displaystyle f(np) \equiv -1 \mod p^3$ for all integers $\displaystyle n.$ therefore for all primes $\displaystyle p > 3$ and all integers $\displaystyle a,b$ we have $\displaystyle \displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \mod p^3.$
Yeah , the key is :

For $\displaystyle p \geq 5$

$\displaystyle \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{p-1} \equiv 0 \bmod{p^2}$

Proof :

Assume $\displaystyle p \neq 2~,~ 3$

$\displaystyle \sum_{k=1}^{p-1} \frac{1}{k} = \ \sum_{k=1}^{(p-1)/2} \left[ \frac{1}{p-k} + \frac{1}{k} \right]$

$\displaystyle = p \sum_{k=1}^{(p-1)/2} \frac{1}{k(p-k)}$

so we are going to show $\displaystyle \sum_{k=1}^{(p-1)/2} \frac{1}{k(p-k)} \equiv 0 \bmod{p}$ we have

$\displaystyle \sum_{k=1}^{(p-1)/2} \frac{1}{k(p-k)} \equiv -\sum_{k=1}^{(p-1)/2} \frac{1}{k^2}$ $\displaystyle \equiv - \sum_{k=1}^{(p-1)/2} k^2 \equiv - \frac{p(p^2-1)}{24} \equiv 0 \bmod{p}$

Therefore , $\displaystyle \frac{1}{1} + \frac{1}{2} + ... + \frac{1}{p-1} \equiv 0 \bmod{p^2}$

5. ## An attempt proof.

For any integer $\displaystyle r$ let $\displaystyle I_r=(rp+1)(rp+2)\cdots(rp+p-1)$, then (*)$\displaystyle I_r\equiv (p-1)!\bmod p^2$; this will be justified later.
With this we can write for some positive integer $\displaystyle k$ the following: $\displaystyle (kp)!=I_0\cdot I_1\cdots I_{k-1}\cdot(1p)(2p)\cdots(kp)=I_0\cdot I_1\cdots I_{k-1}\cdot p^kk!$, and so
(^)$\displaystyle \displaystyle{\frac{(kp)!}{p^kk!}=I_0\cdot I_1\cdots I_{k-1}\equiv [(p-1)!]^k\bmod p^2}$ (I applied the congruence (*)).

Set $\displaystyle c=a-b$ for brevity, so $\displaystyle \displaystyle{A=\binom{ap}{bp}=\frac{(ap)!}{(bp)!( cp)!}}$ and $\displaystyle \displaystyle{B=\binom{a}{b}=\frac{(a)!}{(b)!(c)!} }$. Consider the following $\displaystyle \displaystyle{A\frac{(bp)!}{p^bb!}\frac{(cp)!}{p^c c!}=A\frac{(bp)!(cp)!}{p^ab!c!}=\frac{(ap)!}{p^ab! c!}=\frac{(ap)!}{p^aa!}B}$, the last equality is because $\displaystyle b!c!B=a!$. I write the main equality: (#)$\displaystyle \displaystyle{A\frac{(bp)!}{p^bb!}\frac{(cp)!}{p^c c!}=\frac{(ap)!}{p^aa!}B}$

Now computing (#) modulo $\displaystyle p^2$ and using result (^) we have $\displaystyle A[(p-1)!]^b[(p-1)!]^c\equiv [(p-1)!]^aB\bmod p^2$; $\displaystyle A[(p-1)!]^a\equiv [(p-1)!]^aB\bmod p^2$. Since $\displaystyle [(p-1)!]^a$ is relatively prime to $\displaystyle p^2$, we can arrive at $\displaystyle A\equiv B\bmod p^2$, or $\displaystyle \displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \bmod{p^2}$.

Everything depends now on proving (*). From the expansion of $\displaystyle I_r$ it can be noticed that taking $\displaystyle rp$ from more than one parentheses gives terms that are divisble by $\displaystyle p^2$, therefore $\displaystyle I_r\equiv rp\cdot t+(p-1)!\bmod p^2$, where $\displaystyle t=\frac{(p-1)!}{1}+\frac{(p-1)!}{2}+\cdots+\frac{(p-1)!}{p-1}$.

Consider the polynomial $\displaystyle P(x)=(x-1)(x-2)\cdots(x-(p-1))$. Then, $\displaystyle P(x)=x^{p-1}-s_{p-2}x^{p-2}+\cdots-s_1x^1+s_0$, where $\displaystyle s_1=t, s_0=(p-1)!$. $\displaystyle P(p)\equiv -s_1p+s_0=-tp+(p-1)!\bmod p^2$ and because $\displaystyle P(p)=(p-1)!$ we have $\displaystyle (p-1)!\equiv -tp+(p-1)! \bmod p^2$; or $\displaystyle tp\equiv 0 \bmod p^2$. Divide by $\displaystyle p$, so $\displaystyle t\equiv 0\bmod p$, and $\displaystyle rp\cdot t$ is divisible by $\displaystyle p^2$.

We now can conclude that $\displaystyle I_r\equiv (p-1)! \bmod p^2$.

I hope I'm not missing something...

6. We proceed by induction on $\displaystyle a$, for $\displaystyle a = 0$ it's trivial that $\displaystyle \binom{a\cdot p}{b \cdot p} \equiv_{p^2} \binom{a}{b}$ for all $\displaystyle b\in \mathbb{N}$.

Now assume the assertion holds for $\displaystyle a-1$, let's show it the holds for $\displaystyle a$. - in what follows we consider a > b since it's trivial otherwise.

We have $\displaystyle \binom{a\cdot p}{b \cdot p} = \binom{(a-1)\cdot p + p}{b\cdot p} = \sum_{k=0}^{p} \binom{(a-1)\cdot p}{b\cdot p - k}\cdot \binom{p}{k}=\sum_{k=1}^{p-1}\binom{(a-1)\cdot p}{b\cdot p - k}\cdot \binom{p}{k}+\binom{(a-1)\cdot p}{b\cdot p}+\binom{(a-1)\cdot p}{(b-1)\cdot p}$

Note that if $\displaystyle p$ divides $\displaystyle \sum_{k=1}^{p-1}\binom{(a-1)\cdot p}{b\cdot p - k}\cdot \binom{p}{k}$ we are done, because $\displaystyle \binom{(a-1)\cdot p}{b\cdot p}+\binom{(a-1)\cdot p}{(b-1)\cdot p} \equiv _{p^2} {\binom{a-1}{b}+\binom{a-1}{b-1}=\binom{a}{b} }$ by the inductive hypothesis and Pascal's identity.

Now $\displaystyle \binom{(a-1)\cdot p}{b\cdot p - k} = \frac{((a-1)\cdot p)!}{((a-1-b)\cdot p + k)!\cdot (b\cdot p - k)!}$ . If we denote by $\displaystyle v_p(n)$ the greatest integer r such that $\displaystyle p^r |n!$ then:
$\displaystyle v_p((a-1)\cdot p) = (a-1) + v_p(a-1)$ ;
$\displaystyle v_p((a-1-b)\cdot p + k) = v_p(a-1-b) + a-1-b$ since $\displaystyle 0<k<p$ ;
$\displaystyle v_p(b\cdot p - k) = v_p(b) + b - e_p(b\cdot p)$ where $\displaystyle e_p(n)$ is the greatest r such that $\displaystyle p^r|n$ since $\displaystyle p>k>0$ - you can check this by using Polignac's formula -

Thus $\displaystyle e_p\left(\binom{(a-1)\cdot p}{b\cdot p - k}\right) = e_p\left(\binom{a-1}{b}\right) + e_p(b\cdot p)\geq 1$ and so $\displaystyle p$ divides $\displaystyle \binom{(a-1)\cdot p}{b\cdot p - k}$ for all k = 1,...,p-1 .

But also $\displaystyle \binom{p}{k}$ is a multiple of p for $\displaystyle k = 1, ..., p-1$ and so we are done $\displaystyle \square$