I have the following conjecture on binomials modulo prime powers:
Let $s, b, n \ge 0$ be integers, let $p$ be a prime and let $0\le k_0 < p^{b+1}$ and $0\le n_0 < p^{b+s}$, then we have the following congruence: $$ \binom{n p^{s+b} + n_0}{ k_0} \equiv \binom{n_0}{k_0} \pmod{p^s} . $$
The case $s=1$ follows directly from Lucas' theorem, since: $$ \binom{n p^{1+b} + n_0}{ k_0} \equiv \binom{n}{ 0} \binom{n_0}{k_0} \pmod{p} . $$
The generalization to powers is quite similar to Davis and Webb's Theorem 3 which is a generalization of Lucas' theorem, and says that if $n, k, r, s$ are positive integers then
$$ \binom{n p^{s+b} + n_0}{k p^{s+b} + k_0} \equiv \binom{np^{s-1}}{kp^{s-1}}\binom{n_0}{k_0} \pmod{p^s} . $$
Under the condition that $0\le k_0,n_0 < p^{b+1}$.
The difference is that Davis and Webb have a stronger restriction on $n_0$, while I have a stronger restriction on $k$. (I require $k=0$.)
As far as I can tell there is no way to prove on of the statements from the other. But both numerically appear to be true. (Well, the second one is a theorem, so that's not surprising.)
Can anyone help help me determine if my conjecture is true?
Theorem 1: Let $ p $ be a prime and let $ s $ and $\ell$ be positive integers. For any integers $n$, and $k$, such that $k < p^{\ell}$, write $n=n_1 p^{\ell+s-1} + n_0$ where $ 0 \leq n_0 < p^{\ell+s-1}$. The following congruence holds: \begin{align} \binom{n}{k} \equiv \binom{n_0}{k} \pmod {p^s}.&& (1) \end{align}
The case $s=1$ is easy to prove using the classic result known as Lucas' Theorem: $\binom{n}{k}\equiv\prod_{i=0}^m \binom{n_i}{k_i} \pmod{p}$, where $n=\sum_{i=0}^m n_i p^i$ is the base $p$ expansion of $n$, and $k$ is similarly represented. Since $\binom{n}{0}=1$, and $k_i=0$ for $i \ge \ell$, we can similarly limit $n$ to the first $\ell$ digits, which is exactly $n_0$, as $\ell+s-1=l$ in this case. Lucas Theorem thus gives us directly: $$ \binom{n}{k} \equiv\prod_{i=0}^m \binom{n_i}{k_i} \equiv\prod_{i=0}^\ell \binom{n_i}{k_i} \equiv\binom{n_0}{k} \pmod{p}. $$
The case $s>1$ is more tricky, and we will need some more powerful tools.
Proof: We consider two cases: one, if $p^s$ divides $\binom{n}{k}$; and two, if it doesn't.
Case: $p^s$ divides $\binom{n}{k}$: In the first case, the lhs. of eq. (1) is 0, so we need to show the rhs. is zero too, that is $p^s$ divides $\binom{n_0}{k}$. We'll use Kummer's Theorem, which says: "If $n$ and $k$ are integers and $p$ is a prime, then the largest power of $p$ dividing $\binom n k$ is given by the number of borrows required when subtracting the base $p$ representations of $k$ from $n$." So we need to show that $n_0 - k$ has as many borrows as $n-k$. However, this is clearly the case when $n_0 \ge k$. And when $n_0 < k$ the rhs. of eq. (1) is 0 by the definition of binomial coefficients.
Case: $p^s$ does not divide $\binom{n}{k}$: For the second case, where $p^s$ doesn't divide $\binom{n}{k}$ we will use the following result of Davis and Webb:
Theorem: Let $p$ be any prime, and $s$ be a non-negative integer. Define $n$ and $m$ \begin{align*} n &= n_0 + n_1 p + \ldots + n_{\ell-1} p^{\ell-1}, \\ m &= m_0 + m_1 p + \ldots + m_{\ell-1} p^{\ell-1}. \end{align*} for some $\ell$ large enough, such that $0\le n_i, m_i < p$ for each $i$. Further define the "length $s$ blocks" of $n$ as $$ n[i:i+s] = n_i + n_{i+1} p + \dots + n_{i+s-1} p^{s-1}, $$ and equivalently for $m$.
Then \begin{align*} \\ \text{where} \quad P = \prod_{i=0}^{\ell-s} \binom{n[i:i+s]}{m[i:i+s]} \quad\text{and}\quad Q = \prod_{j=1}^{\ell-s} \binom{n[i:i+s-1]}{m[i:i+s-1]}, \end{align*} and $ Q^{-1} $ denotes the modular multiplicative inverse of $ Q $ modulo $ p^s $.
Note: As a technical detail Davis and Webb redefine the value of the binomial coefficients $\binom{n}{m}$ when $n < m$. Instead of being 0, we define in this case \begin{align*} \binom{n[i:j+1]}{m[i:j+1]} = \begin{cases} \phantom{p} \binom{n[i:j]}{m[i:j]} &\text{if}\quad n_{j} = m_{j} \\ p \binom{n[i:j]}{m[i:j]} & \text{if}\quad n_{j} < m_{j}. \end{cases} \end{align*}
Note: The requirement that $p^s$ does not divide $\binom{n}{k}$ is important. Consider for example $p=2$, $s=2$ and $\ell=3$. Take \begin{align*} n &= 0 + 0\cdot 2 + 1\cdot 2^2 = 4, \\ m &= 1 + 0\cdot 2 + 0\cdot 2^2 = 1. \end{align*} In this case $\binom{4}{1} = 4 \equiv 0 \pmod{2^2}$. But $ P = \binom{0 + 0\cdot 2}{1 + 0\cdot 2} \binom{0 + 1\cdot 2}{0 + 0\cdot 2} = \binom{0}{1} \binom{2}{0} = 2\cdot1 = 2 $ and $ Q=\binom{0}{0}=1. $ So $PQ^{-1}=2 \not\equiv 0 \pmod {2^2}$. Hence special casing $p^s$ divides $\binom{n}{k}$, like we did earlier, is necessary.
We continue to prove the main Theorem in the case $p^s$ divides $\binom{n}{k}$. To avoid issues with notation, let's write it as $\binom{n}{k} \equiv \binom{n'}{k} \pmod {p^s}.$ where $n \equiv n' \pmod{p^{\ell+s-1}}$. Pick $L$ large enough that $n<p^L$. Then applying Davis and Webb's Theorem to the left hand side we get: \begin{align*} P &= \prod_{i=0}^{L-s} \binom{n[i:i+s]}{k[i:i+s]} = \prod_{i=0}^{\ell-1} \binom{n[i:i+s]}{k[i:i+s]} \prod_{i=\ell}^{L-s}\binom{n[i:i+s]}{0} , \\ Q &= \prod_{j=1}^{L-s} \binom{n[i:i+s-1]}{k[i:i+s-1]} = \prod_{j=1}^{\ell-1} \binom{n[i:i+s-1]}{k[i:i+s-1]} \prod_{j=\ell}^{L-s} \binom{n[i:i+s-1]}{0}, \end{align*} Since $k < p^\ell$. Now, as $\binom{n}{0}=1$ for all $n$, we see that the highest $i$ such that the value of $n_i$ matters is $n_{\ell+s-2}$. By definition $n'_i = n_i$ for all $i \le \ell+s-2$, so applying Davis and Webb to the right hand side of eq. (1) we get the same value, proving the original congruence. $\square$