Binomial Coefficient

Printable View

August 10th 2010, 06:20 PM
chiph588@

Binomial Coefficient

For a prime $\displaystyle p$ , show $\displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \bmod{p^2}$ .
August 11th 2010, 01:13 AM
simplependulum

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

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

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

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

$= [(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 $(1+x)^p - 1 - x^p$ are divisible by $p$ .

Then i consider the second polynomial , the annoying one .

$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 $(1+x)^p \equiv 1+ x^p \bmod{p}$ to simplify $P(x)$ :

$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)$

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

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

Remarks :

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

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

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

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

$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 ] +$ $... + [( 1+ x^p )^{a-1} + (1+x^p)^{a-2} A ] + (1+x^p)^{a-1} \bmod{p^2}$

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

$\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 $x^{bp}$ in $P(x)$ is congruent to ( $\bmod{p^3}$ ) that in $[(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 $x^{p}$ in $[(1+x)^p - 1 - x^p ]^2$ is congruent to zero modulo $p^3$ .

ie :

$\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 .
August 11th 2010, 09:15 AM
NonCommAlg

let $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 $(\mathbb{Z}/p\mathbb{Z})[x],$ we have $f(x)=x^{p-1}-1.$

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

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

$\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 $p>3: \ a_{p-2} \equiv 0 \mod p^2.$

thus $f(np) \equiv -1 \mod p^3$ for all integers $n.$ therefore for all primes $p > 3$ and all integers $a,b$ we have $\displaystyle \binom{ap}{bp} \equiv \binom{a}{b} \mod p^3.$
August 11th 2010, 06:02 PM
simplependulum

Quote:

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

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

Yeah , the key is :

For $p \geq 5$

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

Proof :

Assume $p \neq 2~,~ 3$

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

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

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

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

Therefore , $\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{p-1} \equiv 0 \bmod{p^2}$
August 12th 2010, 06:34 PM
melese

An attempt proof.

For any integer $r$ let $I_r=(rp+1)(rp+2)\cdots(rp+p-1)$ , then (*) $I_r\equiv (p-1)!\bmod p^2$ ; this will be justified later.
With this we can write for some positive integer $k$ the following: $(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{\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 $c=a-b$ for brevity, so $\displaystyle{A=\binom{ap}{bp}=\frac{(ap)!}{(bp)!( cp)!}}$ and $\displaystyle{B=\binom{a}{b}=\frac{(a)!}{(b)!(c)!} }$ . Consider the following $\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 $b!c!B=a!$ . I write the main equality: (#) $\displaystyle{A\frac{(bp)!}{p^bb!}\frac{(cp)!}{p^c c!}=\frac{(ap)!}{p^aa!}B}$

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

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

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

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

I hope I'm not missing something...
August 15th 2010, 08:50 AM
PaulRS

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

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

We have $\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 $p$ divides $\sum_{k=1}^{p-1}\binom{(a-1)\cdot p}{b\cdot p - k}\cdot \binom{p}{k}$ we are done, because $\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 $\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 $v_p(n)$ the greatest integer r such that $p^r |n!$ then:
$v_p((a-1)\cdot p) = (a-1) + v_p(a-1)$ ;
$v_p((a-1-b)\cdot p + k) = v_p(a-1-b) + a-1-b$ since $0<k<p$ ;
$v_p(b\cdot p - k) = v_p(b) + b - e_p(b\cdot p)$ where $e_p(n)$ is the greatest r such that $p^r|n$ since $p>k>0$ - you can check this by using Polignac's formula -

Thus $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 $p$ divides $\binom{(a-1)\cdot p}{b\cdot p - k}$ for all k = 1,...,p-1 .

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