Is $p\geq 3$ a prime divisor of $\sum_{t=0}^{\frac{p-1}{m}-1}\sum_{s=0}^{\frac{p-1}{m}-1}\binom{tm}{sm}$ where $m$ divides $p-1~?$

Question

Is it always true that $p\geq 3$ not a prime divisor of \begin{equation*} \sum_{t=0}^{\frac{p-1}{m}-1}\sum_{s=0}^{\frac{p-1}{m}-1}\binom{tm}{sm} \end{equation*} where $m$ divides $p-1~?$

The following is my attempt, and I made some simplifications in order to conclude something. But it seems not to be very helpful. Any comments or advice would be grateful.

\begin{align*} \sum_{t=0}^{\frac{p-1}{m}-1}\sum_{s=0}^{\frac{p-1}{m}-1}\binom{tm}{sm}&=\sum_{t=0}^{\frac{p-1}{m}-1}\left(\binom{tm}{0}+\binom{tm}{m}+\binom{tm}{2m}+\cdots+\binom{tm}{p-1-m}\right)\\ &=\sum_{t=0}^{\frac{p-1}{m}-1}\left(1+\binom{tm}{m}+\binom{tm}{2m}+\cdots+\binom{tm}{p-1-m}\right)\\ &=\frac{p-1}{m}+\sum_{t=0}^{\frac{p-1}{m}-1}\binom{tm}{m}+\sum_{t=0}^{\frac{p-1}{m}-1}\binom{tm}{2m}+\cdots+\sum_{t=0}^{\frac{p-1}{m}-1}\binom{tm}{p-1-m}\\ &=\frac{p-1}{m}+\sum_{t=1}^{\frac{p-1}{m}-1}\binom{tm}{m}+\sum_{t=2}^{\frac{p-1}{m}-1}\binom{tm}{2m}+\cdots+\sum_{t=\frac{p-1}{m}-1}^{\frac{p-1}{m}-1}\binom{tm}{p-1-m}\\ &=1+\frac{p-1}{m}+\sum_{t=1}^{\frac{p-1}{m}-1}\binom{tm}{m}+\sum_{t=2}^{\frac{p-1}{m}-1}\binom{tm}{2m}+\cdots+\sum_{t=\frac{p-1}{m}-2}^{\frac{p-1}{m}-1}\binom{tm}{p-1-2m} \end{align*}

Answer 1

$\def\ZZ{\mathbb{Z}}\def\FF{\mathbb{F}}\def\CC{\mathbb{C}}$I will prove the following:

Theorem Let $m$ be odd. Then there is a constant $N$ such that, if $p$ a prime which is $1 \bmod m$ and $>N$, then the sum in question is $0 \bmod p$.

Thanks to mathlove's answer for many of the key ideas in this answer.

---

To start with, take no hypotheses on $m$ and let $p$ be a prime which is $1 \bmod m$. Since $p \equiv 1 \bmod m$, there are $m$ distinct $m$-th roots of unity in $\FF_p$, call them $\gamma_1$, $\gamma_2$, ..., $\gamma_m$.

Note that we have $$\sum_{n=0}^{p-2} (\gamma_i+\gamma_j)^n = \sum_{n=0}^{p-2} \sum_{k=0}^n \binom{n}{k} \gamma_i^k \gamma_j^{n-k}.$$ Summing on $i$ and $j$, we get $$\sum_{i,j=1}^m \sum_{n=0}^{p-2} (\gamma_i+\gamma_j)^n = \sum_{n=0}^{p-2} \sum_{k=0}^n \binom{n}{k} \sum_{i,j=1}^m \gamma_i^k \gamma_j^{n-k}.$$ The inner sum is $m^2$ if $k \equiv n-k \equiv 0 \bmod m$, and is $0$ otherwise, so we get that $\sum_{i,j=1}^m \sum_{n=0}^{p-2} (\gamma_i+\gamma_j)^n$ is $m^2$ times the sum in question.

Now, for $a \in \FF_p$, we have $$\sum_{n=0}^{p-2} a^n = \begin{cases} 1 & a =0 \\ p-1 & a = 1 \\ 0 & \text{otherwise} \end{cases}.$$ To see the last case, note that, for $a \neq 0$, $1$, we have $$\sum_{n=0}^{p-2} a^n = \frac{a^{p-1}-1}{a-1} = 0.$$

Thus, we need to understand whether $\gamma_i+\gamma_j$ could be $0$ or $1$. Our result will follow from proving the following two lemmas:

Lemma 1: Let $m$ be odd. If $p$ is a prime $>2$ which is $1 \bmod m$ and $\gamma_1$, $\gamma_2$, ..., $\gamma_m$ are the $m$-th roots of unity modulo $p$, then $\gamma_i+\gamma_j \neq 0$.

Lemma 2: Let $m$ not be divisible by $6$. Then there is a constant $N$ such that, if $p$ is a prime $>N$ which is $1 \bmod m$ and $\gamma_1$, $\gamma_2$, ..., $\gamma_m$ are the $m$-th roots of unity modulo $p$, then $\gamma_i+\gamma_j \neq 1$.

Lemma 1 is easier.

Proof of Lemma 1 Suppose that $\gamma_i+\gamma_j = 0$. Then $-1 = \gamma_i \gamma_j^{-1}$, so $-1$ is an $m$-th root of unity. But $m$ is odd and $p>2$, a contradiction. $\square$

To prove Lemma 2, we use resultants.

Lemma 3 For $p$ a prime which is $1 \bmod m$, there are two $m$-th roots of unity in $\FF_p$ with sum $1$ if and only if $p$ divides one of the $m^2$ many resultants $R(x^a+x^b-1, x^m-1)$ for $0 \leq a,b \leq m-1$.

Proof: We recall that $R(x^a+x^b-1, x^m-1) = 0 \bmod p$ if and only if $x^a+x^b-1$ and $x^m-1$ have a common root in the algebraic closure $\overline{\FF}_p$. Since $p \equiv 1 \bmod m$, all roots of $x^m-1$ in $\overline{\FF}_p$ in fact lie in $\FF_p$.

So, if $\zeta$ is a common root of $x^a+x^b-1$ and $x^m-1$, then $\zeta^a$ and $\zeta^b$ are two $m$-th roots of unity in $\FF_p$ summing to $1$.

Conversely, suppose that we have two $m$-th roots of unity, $\alpha$ and $\beta$, in $\FF_p$, which sum to $1$. The group of $m$-th roots of unity in $\FF_p$ is cyclic; let $\zeta$ be a generator and let $\alpha = \zeta^a$ and $\beta = \zeta^b$. Then $\zeta$ is a common root of $x^m-1$ and $x^a+x^b-1$ in $\FF_p$. So we have proven the equivalence. $\square$

Lemma 1 will follow from Lemma 3 as long as none of the resultants $R(x^a+x^b-1, x^m-1)$ are $0$ (just take $N$ larger than any of these resultants). So, to finish the problem, we must show:

Lemma 4: Let $m$ be not divisible by $6$. Then the restultant $R(x^a+x^b-1, x^m-1)$ is not $0$ for any $0 \leq a,b \leq m-1$.

Proof: If $R(x^a+x^b-1, x^m-1)=0$, then the polynomials $x^a+x^b-1$ and $x^m-1$ have a common root in $\CC$. So there are two $m$-th roots of unity in $\CC$ which add to $1$. But the only two numbers on the unit circle which sum to $1$ are $\tfrac{1 \pm \sqrt{-3}}{2}$, which are primitive $6$-th roots of unity. So, since $m$ is not divisible by $6$, these are not $m$-th roots of unity. $\square$

This concludes the proof of the Theorem.

---

I'll note that the prime factors of these resultants can be surprisingly large! Here is a table of all the factors for the first few values of $m$:

m     prime factors of resultants
3     2, 7
5     11, 31
7     2, 29, 127
9     2, 7, 19, 37, 73
11    23, 67, 89, 199
13    3, 53, 79, 131, 521, 8191

---

I haven't checked this as carefully, but you should be able to use the same argument to work out what the sum equals when $m$ is even, and $p$ is large enough not to divide any of the nonzero resultants. I believe that, for $m \equiv 2,4 \bmod 6$, the sum is $\tfrac{1}{m^2} m$ (coming from the $m$ pairs $(\zeta, - \zeta)$ of $m$-th roots of unity summing to $0$) and, for $m \equiv 0 \bmod 6$, we get $\tfrac{1}{m^2} (m-2)$, where we add in the $m$ pairs $(\zeta, - \zeta)$ as above, and then subtract of $2$ for $(\eta, \eta^{-1})$ and $(\eta^{-1}, \eta)$, where $\eta$ is a primitive $6$-th root of unity.

Answer 2

Let $$S(m,p):=\sum_{t=0}^{\frac{p-1}{m}-1}\sum_{s=0}^{\frac{p-1}{m}-1}\binom{tm}{sm}$$

In the following, let us prove the followings :

• $S(1,p)$ is divisible by $p$.

• $S(2,p)$ is not divisible by $p$.

• $S(3,7)$ is not divisible by $7$.

• If $p\ge 13$, then $S(3,p)$ is divisible by $p$.

• $S(4,p)$ is not divisible by $p$.

• $S(5,11)$ is not divisible by $11$.

• $S(5,31)$ is not divisible by $31$.

• If $p\ge 41$, then $S(5,p)$ is divisible by $p$.

---

Using that $\binom nk=0$ when $n\lt k$, $S(m,p)$ can be simplified as $$S(m,p)=\sum_{t=0}^{\frac{p-1}{m}-1}\sum_{s=0}^{t}\binom{tm}{sm}$$

Here, we have $$\sum_{s=0}^{t}\binom{tm}{sm}=\begin{cases}1&\text{if $m\ge 1$ and $t=0$} \\\\ 2^t&\text{if $m=1$ and $t\ge 1$} \\\\ \dfrac{2^{tm}}{m}+\dfrac{2^{tm+1}}{m}\displaystyle\sum^{\lfloor m/2\rfloor}_{k=1}(-1)^{kt}\cos^{tm}\bigg(\frac{k\pi}{m}\bigg)&\text{if $m\ge 2$ and $t\ge 1$}\end{cases}$$

(A proof is written at the end of this answer.)

Therefore, for $m\ge 2$, we get $$\begin{align}S(m,p)&=\sum_{t=0}^{\frac{p-1}{m}-1}\sum_{s=0}^{t}\binom{tm}{sm} \\\\&=1+\bigg(\sum_{t=1}^{\frac{p-1}{m}-1}\dfrac{2^{tm}}{m}\bigg)+\sum_{t=1}^{\frac{p-1}{m}-1}\dfrac{2^{tm+1}}{m}\displaystyle\sum^{\lfloor m/2\rfloor}_{k=1}(-1)^{kt}\cos^{tm} \frac{k\pi}{m} \\\\&=1+\frac{2^{p-1}-2^m}{m(2^m-1)}+\frac 2m\sum_{t=1}^{\frac{p-1}{m}-1}\sum^{\lfloor m/2\rfloor}_{k=1}(-1)^{kt}\bigg(2\cos\frac{k\pi}{m}\bigg)^{tm}\end{align}$$

---

For $m=1$, $$S(1,p)=\sum_{t=0}^{p-2}\sum_{s=0}^{t}\binom{t}{s}=1+\sum_{t=1}^{p-2}2^t=2^{p-1}-1$$ Since $2^{p-1}\equiv 1\pmod p$, this is divisible by $p$.

---

For $m=2$, $$S(2,p)=\frac{2^{p-1}+2}{6}+\sum_{t=1}^{\frac{p-1}{2}-1}(-1)^{t}\bigg(2\cos\frac{\pi}{2}\bigg)^{2t}=\frac{2^{p-2}+1}{3}$$ This is not divisible by $p$.

---

For $m=3$, $$S(3,p)=\frac{2^{p-1}+13}{21}+\frac 23\sum_{t=1}^{\frac{p-4}{3}}(-1)^{t}=\frac{2^{p-1}+13}{21}-\frac 23=\frac{2^{p-1}-1}{21}$$

• $S(3,7)=3$ is not divisible by $7$.

• If $p\ge 13$, then $S(3,p)$ is divisible by $p$.

---

For $m=4$, $$\begin{align}S(4,p)&=\frac{2^{p-1}+44}{60}+\frac 12\sum_{t=1}^{\frac{p-1}{4}-1}\sum^{2}_{k=1}(-1)^{kt}\bigg(2\cos\frac{k\pi}{4}\bigg)^{4t} \\\\&=\frac{2^{p-1}+44}{60}+\frac 12\sum_{t=1}^{\frac{p-1}{4}-1}(-4)^t \\\\&=\frac{2^{p-1}+20-6(-4)^{(p-1)/4}}{60}\end{align}$$

This is not divisible by $p$.

(The reason is as follows : If this is divisible by $p$, we have to have $$7\equiv 2(-4)^{(p-1)/4}\pmod p\implies 7^4\equiv 16\pmod p\implies p=5,53$$ which are not sufficient.)

---

For $m=5$,

With help of WolframAlpha,

$$\begin{align}S(5,p)&=\frac{2^{p-1}+123}{155}+\frac 25\sum_{t=1}^{\frac{p-1}{5}-1}\sum^{2}_{k=1}(-1)^{kt}\bigg(2\cos\frac{k\pi}{5}\bigg)^{5t} \\\\&=\frac{2^{p-1}+123}{155} \\&\qquad -\frac{9\cdot 2^{p + 1} - (19 - 9 \sqrt 5) (\sqrt 5+1)^p + (19 + 9 \sqrt 5) (\sqrt 5 - 1)^p}{55\cdot 2^p} \\\\&=\frac{A}{5\times 11\times 31\times 2^p}\end{align}$$

where $$\begin{align}A&=11\cdot 2^p(2^{p-1}+123)-31\cdot 9\cdot 2^{p+1} \\&\qquad +31(19-9\sqrt 5)(\sqrt 5+1)^p-31(19+9\sqrt 5)(\sqrt 5-1)^p \\\\&=11\cdot 2^{2p-1}+795\cdot 2^p+31\times 19\bigg((\sqrt 5+1)^p-(\sqrt 5-1)^p\bigg) \\&\qquad -31\times 9\sqrt 5\bigg((\sqrt 5+1)^p+(\sqrt 5-1)^p\bigg) \\\\&=11\cdot 2^{2p-1}+795\cdot 2^p+31\times 19\sum_{i=1}^{(p+1)/2}\binom{p}{2i-1}2(\sqrt 5)^{p-(2i-1)} \\&\qquad -31\times 9\sum_{i=0}^{(p-1)/2}\binom{p}{2i}2(\sqrt 5)^{p-2i+1}\end{align}$$

• $S(5,11)=3$ is not divisible by $11$.

• $S(5,31)=6865813$ is not divisible by $31$.

• If $p\ge 41$, then $S(5,p)$ is divisible by $p$.

(The reason is as follows : Since $2^{p-1}\equiv 1\pmod p$ and $\binom pi\equiv 0\pmod p$ when $1\le i\le p-1$, we have $A\equiv 2790-2790(\frac 5p)\equiv 2790-2790\frac{1}{(\frac p5)}\equiv 0\pmod p$ where $(\frac{b}{a})$ denotes the Legendre symbol. Since the denominator has $11$ and $31$, it is sufficient that $p\ge 41$.)

---

In the following, let us prove that if $m\ge 2$ and $t\ge 1$, then

$$\sum_{s=0}^{t}\binom{tm}{sm}=\dfrac{2^{tm}}{m}+\dfrac{2^{tm+1}}{m}\displaystyle\sum^{\lfloor m/2\rfloor}_{k=1}(-1)^{kt}\cos^{tm}\bigg(\frac{k\pi}{m}\bigg)$$

Proof :

Let $\omega:=\cos\frac{2\pi}{m}+i\sin\frac{2\pi}{m}$. Let us consider $$\begin{align}(1+1)^n&=\binom n0+\binom n1+\binom n2+\cdots +\binom nn \\\\(1+\omega)^n&=\binom n0+\binom n1\omega+\binom n2\omega^2 +\cdots +\binom nn\omega^n \\\\&\vdots \\\\(1+\omega^{m-1})^n&=\binom n0+\binom n1\omega^{m-1}+\binom n2(\omega^{m-1})^2+\cdots +\binom nn(\omega^{m-1})^n \end{align}$$

For $k$ such that $m\not\mid k$, the sum of the coefficients of $\binom nk$ is $$1+\omega^k+\omega^{2k}+\cdots +(\omega^{m-1})^k=\frac{\omega^{mk}-1}{\omega^k-1}=0$$ so we get $$\sum_{k=0}^{m-1}(1+\omega^k)^n=m\sum_{s=0}^{\lfloor n/m\rfloor}\binom{n}{sm}$$

Therefore, we can write $$\begin{align}\sum_{s=0}^{\lfloor n/m\rfloor}\binom{n}{sm}&=\frac 1m\sum_{k=0}^{m-1}(1+\omega^k)^n \\\\&=\frac 1m\sum_{k=0}^{m-1}\bigg(1+\cos\frac{2k\pi}{m}+i\sin\frac{2k\pi}{m}\bigg)^n \\\\&=\frac 1m\sum_{k=0}^{m-1}\bigg(2\cos^2\frac{k\pi}{m}+2i\cos\frac{k\pi}{m}\sin\frac{k\pi}{m}\bigg)^n \\\\&=\frac 1m\sum_{k=0}^{m-1}2^n\cos^n\frac{k\pi}{m}\bigg(\cos\frac{kn\pi}{m}+i\sin\frac{kn\pi}{m}\bigg) \\\\&=\frac{2^n}{m}+\frac{2^n}{m}\sum_{k=\color{red}1}^{m-1}f(k)\end{align}$$ where $$f(k)=\cos^n\frac{k\pi}{m}\bigg(\cos\frac{kn\pi}{m}+i\sin\frac{kn\pi}{m}\bigg)$$

Since

• If $m$ is even, then $f(\lfloor m/2\rfloor)=0$

• $f(m-k)=\cos^n\frac{k\pi}{m}\bigg(\cos\frac{kn\pi}{m}\color{red}-i\sin\frac{kn\pi}{m}\bigg)$

we have $$\begin{align}\sum_{s=0}^{\lfloor n/m\rfloor}\binom{n}{sm}&=\frac{2^n}{m}+\frac{2^n}{m}\sum_{k=1}^{m-1}f(k) \\\\&=\frac{2^n}{m}+\frac{2^n}{m}\sum_{k=1}^{\lfloor m/2\rfloor}\bigg(f(k)+f(m-k)\bigg) \\\\&=\frac{2^n}{m}+\frac{2^n}{m}\sum_{k=1}^{\lfloor m/2\rfloor}2\cos^n\frac{k\pi}{m}\cos\frac{kn\pi}{m}\end{align}$$

Therefore, for $n=tm$, we have $$\sum_{s=0}^{t}\binom{tm}{sm}=\dfrac{2^{tm}}{m}+\dfrac{2^{tm+1}}{m}\displaystyle\sum^{\lfloor m/2\rfloor}_{k=1}(-1)^{kt}\cos^{tm}\bigg(\frac{k\pi}{m}\bigg).\ \blacksquare$$