Prove that,
\[\displaystyle\binom{pa}{pb}\equiv\binom{a}{b} (mod p)\]
for all integers $p$, $a$ and $b$ with $p$ a prime, and $a\geq b\geq 0$.
Putnam, 1977: Binomial Residue
Re: Putnam, 1977: Binomial Residue
Suppose, the base-$p$ representation of $a$ and $b$ are respectively:
$a=p^ka_k+p^{k-1}a_{k-1}+.....+p^1a_1+p^0a_0$, and,
$b=p^kb_k+p^{k-1}b_{k-1}+.....+p^1b_1+p^0b_0$.
Now, since, $p$ is a prime, Lucas' Theorem states that,
\[\displaystyle\binom{a}{b}\equiv\binom{a_k}{b_k}\binom{a_{k-1}}{b_{k-1}}......\binom{a_1}{b_1}\binom{a_0}{b_0}(modp)\]
I think the problem should be a lot easier now.
$a=p^ka_k+p^{k-1}a_{k-1}+.....+p^1a_1+p^0a_0$, and,
$b=p^kb_k+p^{k-1}b_{k-1}+.....+p^1b_1+p^0b_0$.
Now, since, $p$ is a prime, Lucas' Theorem states that,
\[\displaystyle\binom{a}{b}\equiv\binom{a_k}{b_k}\binom{a_{k-1}}{b_{k-1}}......\binom{a_1}{b_1}\binom{a_0}{b_0}(modp)\]
I think the problem should be a lot easier now.
Re: Putnam, 1977: Binomial Residue
Still no solution.......... OK, here is mine:
According to the above definition:
$pa=p^{k+1}a_k+p^{k}a_{k-1}+......+p^1a_0+p^0.0$, and,
$pb=p^{k+1}b_k+p^{k}b_{k-1}+......+p^1b_0+p^0.0$
So, from Lucas' Theorem, we get,
\[\displaystyle\binom{pa}{pb}\equiv\binom{a_k}{b_k}\binom{a_{k-1}}{b_{k-1}}.....\binom{a_0}{b_0}\binom{0}{0}(modp)\]
\[\displaystyle\Rightarrow\binom{pa}{pb}\equiv\binom{a_k}{b_k}\binom{a_{k-1}}{b_{k-1}}.....\binom{a_0}{b_0}.1(modp)\]
\[\displaystyle\Rightarrow\binom{pa}{pb}\equiv\binom{a_k}{b_k}\binom{a_{k-1}}{b_{k-1}}.....\binom{a_0}{b_0}(modp)\]
\[\displaystyle\Rightarrow\binom{pa}{pb}\equiv\binom{a}{b}(modp)\]
According to the above definition:
$pa=p^{k+1}a_k+p^{k}a_{k-1}+......+p^1a_0+p^0.0$, and,
$pb=p^{k+1}b_k+p^{k}b_{k-1}+......+p^1b_0+p^0.0$
So, from Lucas' Theorem, we get,
\[\displaystyle\binom{pa}{pb}\equiv\binom{a_k}{b_k}\binom{a_{k-1}}{b_{k-1}}.....\binom{a_0}{b_0}\binom{0}{0}(modp)\]
\[\displaystyle\Rightarrow\binom{pa}{pb}\equiv\binom{a_k}{b_k}\binom{a_{k-1}}{b_{k-1}}.....\binom{a_0}{b_0}.1(modp)\]
\[\displaystyle\Rightarrow\binom{pa}{pb}\equiv\binom{a_k}{b_k}\binom{a_{k-1}}{b_{k-1}}.....\binom{a_0}{b_0}(modp)\]
\[\displaystyle\Rightarrow\binom{pa}{pb}\equiv\binom{a}{b}(modp)\]
Re: Putnam, 1977: Binomial Residue
This is a too weak version Wolstenholme's Theorem
One one thing is neutral in the universe, that is $0$.