Binomial Coefficients involving Prime Powers Minus 1

The claim is true. Summary: we show by induction it is enough to prove the congruence for $A_m$ for $m = 1,\ldots, k$ where $N+1 = p^k$, and then we prove that by showing (in this particular case) that the binomial coefficients are all divisible by $p^k$ (which doesn't hold in general).

Let $$A_m = \sum_{j=0}^{m} \binom{Nm}{Nj}.$$ The claim to be proven is $A_m \equiv 2 \mod N+1$ if $N + 1 = p^k$ is a prime power.

Note that

$$(1 + x)^{Nm} = \sum_{j=0}^{Nm} \binom{Nm}{j} x^j,$$

if one lets $\zeta$ denote a primitive $N$th root of unity, then

$$ \sum_{i=0}^{N-1} (1 + \zeta^i)^{Nm} = \sum_{j=0}^{Nm} \binom{Nm}{j} \sum_{i=0}^{N-1} \zeta^{ji}$$ $$ = \sum_{j=0}^{Nm} \binom{Nm}{j} \begin{cases} N, & j \equiv 0 \mod N \\ 0, & j \not\equiv 0 \mod N. \end{cases}$$ $$ = N \sum_{j=0}^{m} \binom{Nm}{Nj}.$$ So if, for $m \ge 1$, $$B_m = \sum_{i=0}^{N-1} (1 + \zeta^i)^{Nm} = \sum_{\zeta^i \ne -1} (1 + \zeta^i)^{Nm},$$ then the congruence $A_m \equiv 2 \mod (N+1)$ is equivalent to the congruence $B_m \equiv - 2 \mod (N+1)$.

The roots of unity are all distinct modulo $p$, so there is a unique $\zeta^i \equiv -1 \mod p$. If $p$ is odd, then $N$ is even, and it is $\zeta^{i} = -1$, and $(1 + \zeta^i) = 0$. If $p = 2$, then $N$ is odd, and it is $\zeta^i = 1$ and $(1 + \zeta^i) = 2$. In the latter case, for $m \ge 1$, the term $(1 + \zeta^i)^N$ is equal to $2^N$ which is certainly trivial modulo $2^k = N+1$ because $2^N \ge N+1 = 2^k$. Hence we have

$$B_m = \sum_{\zeta^i \ne -1} (1 + \zeta^i)^{Nm} \equiv \sum_{\zeta^i \not\equiv -1} (1 + \zeta^i)^{Nm} \mod p^k.$$

The polynomial $X^N - 1$ is separable over $\mathbf{F}_p$. Moreover, its roots over this field are precisely the units of $\mathbf{F}_q$, since the units in that field are cyclic of order $q - 1 = N$. Hence the extension cut out by the roots of unity $\zeta^i$ over $\mathbf{Q}_p$ is just the fraction field of the Witt vectors $W(\mathbf{F}_q)$. All of this is just to say (if you don't know algebraic number theory) that it makes sense to talk of congruences for these algebraic integers modulo powers of $p$, and that we also have (assuming $\zeta^i \not\equiv -1 \mod p$): $$(1 + \zeta^i)^N \equiv 1 \mod p$$ Hence it also follows that $$((1 + \zeta^i)^{N} - 1)^k \equiv 0 \mod p^k$$ But then, for any non-negative integer $r$, we have: $$\sum_{\zeta^i \not\equiv -1} ((1 + \zeta^i)^{N} - 1)^k (1 + \zeta^i)^{Nr} \equiv 0 \mod p^k,$$ or, expanding out: $$ \sum_{r=0}^{k} B_{n+ r} (-1)^r \binom{k}{r} \equiv 0 \mod p^k,$$ and thus we obtain the $k$-term recurrence $$B_{n+k} (-1)^{k-1} = \sum_{r=0}^{k-1} B_{n+r} (-1)^r \binom{k}{r} \mod p^k$$ Suppose that $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, k$. Then, by induction, we get $B_m \equiv -2 \mod p^k$ for all $m$, simply by applying the recurrence above and using the identity $$\sum (-1)^r \binom{k}{r} = 0.$$ So we just need to prove the first few values of $A_m \equiv 2 \mod p^k$. But now we can look at the actual binomial coefficients themselves.

Suppose that $N+1 = p^k$. We claim that, in the range $a+b \le k$ and $a,b > 0$, we have $$\binom{N(a+b)}{Nb} \equiv 0 \mod p^k.$$ Once we know this, it follows that $A_m \equiv 2 \mod p^k$ for $m \le k$ and we are done by induction.

In fact, since trivially $k \le p^k$, we are done by the following stronger claim.

Claim Suppose that $a + b \le p^k$ and $N + 1 = p^k$. Then the $p$-adic valuation of $$\binom{N(a+b)}{Nb}$$ for $a,b \ge 1$ is exactly $k$.

Proof

The $p$-adic valuation of the binomial coefficient is precisely the number of times one has to carry the one when adding $Na$ and $Nb$. For a number $0 \le m-1 < p^k$ (which includes $a-1$, $b-1$, and $c = a+b-1$, we may write $$m - 1 = (m_{k-1}, m_{k-2}, \ldots, m_0)$$ in base $p$, and we may also write $$p^k - m = (p^k - 1) - (m - 1) = (m'_{k-1}, m'_{k-2}, \ldots, m'_0).$$ Since $$m-1 + (p^k - m) = p^k - 1,$$ we have, for all $i = 0,1,\ldots,k-1$, that $$m_i + m'_i = p - 1.$$ We now find that $aN$, $bN$, and $cN$ have $p$-adic expansions as follows $$aN = (a_{k-1}, a_{k-2}, \ldots, a_0,a'_{k-1}, \ldots, a'_0),$$ $$bN = (b_{k-1}, b_{k-2}, \ldots, b_0,b'_{k-1}, \ldots, b'_0),$$ $$cN = (c_{k-1}, c_{k-2}, \ldots, c_0,c'_{k-1}, \ldots, c'_0),$$ As noted before, we have $$a_i + a'_i = p-1, \ b_i + b'_i = p-1, c_i + c'_i = p -1.$$ Hence $$(a_i + b_i) + (a'_i + b'_i) = (c_i + c'_i) + p - 1,$$ or $$(a_i + b_i - c_i) + (a'_i + b'_i - c'_i) = p - 1.$$

Now

$$a_i + b_i = c_i + \begin{cases} p & \text{carry required} \\ 0 & \text{no carry required}\end{cases} \ + \begin{cases} -1 & \text{carry required in $i-1$ slot} \\ 0 & \text{no carry required in $i-1$ slot} \end{cases}$$ and the same with $a'_i$, $b'_i$, and $c'_i$.

There is a unique way of writing $p-1$ as a sum of exactly two terms in the set $\{p,0,-1,0\}$. It follows that in the pair of slots $(i,i+k)$, either exactly one of the pairs coming from the $m_i$-coefficient and the $m'_i$ coefficient requires "carrying the one," (It also follows that exactly one of the pairs $m_{i-1}$ and $m'_{i-1}$ (which might be $m'_k$ if $i = 0$) also requires carrying the one, although this is the same statement for $i-1$ instead of $i$. This is why the sum is $p-1$ and not $p$.)

But since exactly one of the pair coming from the $m_i$-coefficient and the $m'_i$ coefficient requires "carrying the one," exactly half the terms have this property, and we are done.

Additional: A weaker version of the induction argument is as follows. By the analog of Fermat's Little Theorem and Euler's Theorem in $W(\mathbf{F}_q)$ ($q = p^k$), one has the identity $$\gamma^{N p^{k-1}} = \gamma^{(q-1)p^{k-1}} \equiv 1 \mod p^k$$ for any $\gamma \in W(\mathbf{F}_q)^{\times}$, that is, any $\gamma \not\equiv 0 \mod p$. It follows that

$$\begin{aligned} B_{m + p^{k-1}} = & \ \sum_{\zeta^i \not\equiv - 1} (1 + \zeta^i)^{mN + N p^{k-1}}\\ \equiv & \ \sum_{\zeta^i \not\equiv - 1} (1 + \zeta^i)^{mN} \mod p^k\\ = & \ B_m \mod p^k, \end{aligned}$$ and so by induction it suffices to show that $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, p^{k-1}$ rather than $m = 1, \ldots, k$. Since the second step actually proves the congruence $B_m \equiv -2 \mod p^k$ for $m = 1, \ldots, p^k$, this also suffices, and one might find this version of the inductive step slightly easier.