Babbage's Congruence

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $p$ be a prime number.

Let $a, b \in \Z$ be integers.


Then:

$\dbinom {a p} {b p} \equiv \dbinom a b \pmod {p^2}$

where $\dbinom a b$ denotes a binomial coefficient.


Proof

By Lucas' Theorem, for $a, b \in \mathbb Z_{\ge 0}$:

$\dbinom {a p} {b p} \equiv \dbinom {\floor {a p / p}} {\floor {b p / p}} \dbinom {a \mod p} {b \mod p} \pmod p$

Proof by Mathematical Induction on $a$:

For all $a \in \Z$, let $\map P a$ be the proposition:

$\forall b \in \Z: \dbinom {a p} {b p} \equiv \dbinom a b \pmod {p^2}$


Basis for the Induction

$\map P 0$ is the case:

$\forall b \in \Z: \dbinom 0 {b p} \equiv \dbinom 0 b \pmod {p^2}$

For $b = 0$, we have $\dbinom 0 0 \equiv \dbinom 0 0 \pmod {p^2}$.

For $b \ne 0$, by Zero Choose n:

$\dbinom 0 {b p} = 0 = \dbinom 0 b \equiv \dbinom 0 b \pmod {p^2}$

Hence $\map P 0$ is true.


$\map P {-1}$ is the case:

$\forall b \in \Z: \dbinom {-p} {b p} \equiv \dbinom {-1} b \pmod {p^2}$




Induction Hypothesis

Now we need to show that, if $\map P k$ is true, then it logically follows that $\map P {k + 1}$ and $\map P {k - 1}$ are true.


So this is our induction hypothesis:

$\forall b \in \Z: \dbinom {k p} {b p} \equiv \dbinom k b \pmod {p^2}$


Then we need to show:

$\forall b \in \Z: \dbinom {\paren {k + 1} p} {b p} \equiv \dbinom {\paren {k + 1} } b \pmod {p^2}$
$\forall b \in \Z: \dbinom {\paren {k - 1} p} {b p} \equiv \dbinom {\paren {k - 1} } b \pmod {p^2}$


Induction Step

This is our induction step:

Let $r \in \Z$ and $0 < r < p$.

By Binomial Coefficient of Prime:

$\dbinom p r \equiv 0 \pmod p$

By Lucas' Theorem and Zero Choose n:

$\dbinom {k p} {b p - r} \equiv \dbinom {\floor {k p / p}} {\floor {\paren {b p - r} / p}} \dbinom {k p \bmod p} {b p - r \bmod p} \equiv \dbinom k {b - 1} \dbinom 0 {p - r} \equiv 0 \pmod p$

Therefore:

$(1): \dbinom {k p} {b p - r} \dbinom p r \equiv 0 \pmod {p^2}$


On the other hand, by Lucas' Theorem and Negated Upper Index of Binomial Coefficient:

$\dbinom {-p} r = \paren {-1}^r \dbinom {p + r - 1} r \equiv \paren {-1}^r \dbinom {\floor {\paren {p + r - 1} / p}} {\floor {r / p}} \dbinom {p + r - 1 \bmod p} {r \bmod p} \pmod p$

In particular, $\dbinom {p + r - 1 \bmod p} {r \bmod p} = \dbinom {r - 1 \bmod p} {r \bmod p}$.

Note that $r - 1 \bmod p < r \bmod p$ except when $r \bmod p = 0$.

Hence $\dbinom {-p} r \equiv 0 \pmod p$ except when $p \divides r$.

Therefore, for $p \nmid r$:

$(2): \dbinom {k p} {b p - r} \dbinom {-p} r \equiv 0 \pmod {p^2}$


Now, for $b \ge 0$:

\(\ds \binom {\paren {k + 1} p} {b p}\) \(=\) \(\ds \sum_{r \mathop = 0}^{b p} \binom {k p} {b p - r} \binom p r\) Chu-Vandermonde Identity
\(\ds \) \(=\) \(\ds \sum_{r \mathop = 0}^p \binom {k p} {b p - r} \binom p r\) Definition of Binomial Coefficient: $\dbinom p r = 0$ for $r > p$
\(\ds \) \(\equiv\) \(\ds \binom {k p} {b p - 0} \binom p 0 + \binom {k p} {b p - p} \binom p p\) \(\ds \pmod {p^2}\) by $(1)$ above
\(\ds \) \(\equiv\) \(\ds \binom k b \times 1 + \binom k {b - 1} \times 1\) \(\ds \pmod {p^2}\) Induction Hypothesis, Binomial Coefficient with Zero, Binomial Coefficient with Self
\(\ds \) \(\equiv\) \(\ds \binom {k + 1} b\) \(\ds \pmod {p^2}\) Pascal's Rule
\(\ds \binom {\paren {k - 1} p} {b p}\) \(=\) \(\ds \sum_{r \mathop = 0}^{b p} \binom {k p} {b p - r} \binom {-p} r\) Chu-Vandermonde Identity
\(\ds \) \(\equiv\) \(\ds \sum_{r' \mathop = 0}^b \binom {k p} {b p - r' p} \binom {-p} {r' p}\) \(\ds \pmod {p^2}\) by $(2)$ above, using $r = r' p$
\(\ds \) \(\equiv\) \(\ds \sum_{r' \mathop = 0}^b \binom k {b - r'} \binom {-1} {r'}\) \(\ds \pmod {p^2}\) Induction Hypothesis and Base Case: $a = -1$
\(\ds \) \(\equiv\) \(\ds \binom {k - 1} b\) \(\ds \pmod {p^2}\) Chu-Vandermonde Identity




So $\map P k \implies \map P {k + 1} \land \map P {k - 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

$\forall a, b \in \Z: \dbinom {a p} {b p} \equiv \dbinom a b \pmod {p^2}$

$\blacksquare$

Also see


Source of Name

This entry was named for Charles Babbage.


Sources