If $p^{n-1} + \cdots + p + 1$ divides $\sum\limits_{k=1}^m p^{j_k}(p^{i_k - 1} + \cdots p + 1)$, then $n$ divides $\sum\limits_{k=1}^m i_k$?

Question

Suppose that $p$ is a prime and $m,n$ are positive integers. If $p^{n-1} + \cdots + p + 1$ divides $\sum\limits_{k=1}^m p^{j_k}(p^{i_k - 1} + \cdots p + 1)$, why is it that $n$ divides $\sum\limits_{k=1}^m i_k$, where the $i_k$ and $j_k$ are non-negative integers?

This is a fact that a proof presented in some notes for my number theory course boils down to, but I can't quite see what argument could work here. I should add that it's possible that it's only true for certain values of $p$ and $n$.

Any help would be appreciated. Thanks in advance!

Answer 1

Multiplying both $p^{n-1} + \cdots + p + 1$ and $\sum\limits_{k=1}^m p^{j_k}(p^{i_k - 1} + \cdots p + 1)$ by $p-1$, we obtain that $p^n-1$ divides $\sum\limits_{k=1}^m p^{j_k}(p^{i_k} - 1)$. In general, when $j_k$ are distinct we have to take into account not only the numbers $i_k$, but $j_k$ too. But even when all $j_k$ are equal, the claim can fail. For instance, when $p=2$, $n=2$, $m=3$, $j_1=j_2=j_3=0$, and $i_1=i_2=i_3=1$ we have $p^n-1=3$, $\sum\limits_{k=1}^m p^{j_k}(p^{i_k} - 1)=3$, but $n=2\not|3=\sum\limits_{k=1}^m i_k$.

Answer 2

Alex Ravsky has already provided a good answer which shows a counterexample to your claim which is equivalent to the claim that if $(p^n-1)\mid\sum\limits_{k=1}^m p^{j_k}(p^{i_k}-1)$, then $n\mid \sum\limits_{k=1}^m i_k$.

In the following, I'm going to prove some claims which might interest you.

Claim 1 : If $(x^2-1)\mid\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$, then $2\mid \sum\limits_{k=1}^m i_k$.

Claim 2 : If $(x^3-1)\mid\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$, then $3\mid \sum\limits_{k=1}^m i_k$.

Claim 3 : If $(x^4-1)\mid\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$, then $4\mid \sum\limits_{k=1}^m i_k$.

---

Claim 1 : If $(x^2-1)\mid\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$, then $2\mid \sum\limits_{k=1}^m i_k$.

Proof :

Let $f(x):=\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$.

Let $A$ be the number of terms where $i_k$ is odd and $j_k$ is even.

Let $B$ be the number of terms where $i_k$ is odd and $j_k$ is odd.

We have $0=f(-1)=-2A+2B$ which implies $B=A$, and then $$\sum\limits_{k=1}^m i_k\equiv A+B\equiv 2A\equiv 0\pmod 2.\ \blacksquare$$

---

Claim 2 : If $(x^3-1)\mid\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$, then $3\mid \sum\limits_{k=1}^m i_k$.

Proof :

Let $g(x):=\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$.

Let $A$ be the number of terms where $i_k\equiv 1\pmod 3$ and $j_k\equiv 0\pmod 3$.

Let $B$ be the number of terms where $i_k\equiv 1\pmod 3$ and $j_k\equiv 1\pmod 3$.

Let $C$ be the number of terms where $i_k\equiv 1\pmod 3$ and $j_k\equiv 2\pmod 3$.

Let $D$ be the number of terms where $i_k\equiv 2\pmod 3$ and $j_k\equiv 0\pmod 3$.

Let $E$ be the number of terms where $i_k\equiv 2\pmod 3$ and $j_k\equiv 1\pmod 3$.

Let $F$ be the number of terms where $i_k\equiv 2\pmod 3$ and $j_k\equiv 2\pmod 3$.

Let $\omega=\dfrac{-1+\sqrt 3\ i}{2}$. Using $\omega^3=1$ and $\omega^2=-\omega-1$, we have $$\begin{align}0&=g(\omega) \\\\&=A(\omega-1)+B\omega(\omega-1)+C\omega^2(\omega-1)+D(\omega^2-1) \\&\qquad +E\omega(\omega^2-1)+F\omega^2(\omega^2-1) \\\\&=(A-2B+C-D-E+2F)\omega-A-B+2C-2D+E+F\end{align}$$ which implies $$-A-B+2C-2D+E+F=0\tag1$$

From $(1)$, we get $$\begin{align}\sum\limits_{k=1}^m i_k&\equiv A+B+C+2(D+E+F)\pmod 3 \\\\&\equiv A+B+C+2(D+E+F) \\&\qquad +(-A-B+2C-2D+E+F)\pmod 3 \\\\&\equiv 3(C+E+F)\pmod 3 \\\\&\equiv 0\pmod 3.\ \blacksquare\end{align}$$

---

Claim 3 : If $(x^4-1)\mid\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$, then $4\mid \sum\limits_{k=1}^m i_k$.

Proof :

Let $h(x):=\sum\limits_{k=1}^m x^{j_k}(x^{i_k}-1)$.

Let $A$ be the number of terms where $i_k\equiv 1\pmod 4$ and $j_k\equiv 0\pmod 4$.

Let $B$ be the number of terms where $i_k\equiv 1\pmod 4$ and $j_k\equiv 1\pmod 4$.

Let $C$ be the number of terms where $i_k\equiv 1\pmod 4$ and $j_k\equiv 2\pmod 4$.

Let $D$ be the number of terms where $i_k\equiv 1\pmod 4$ and $j_k\equiv 3\pmod 4$.

Let $E$ be the number of terms where $i_k\equiv 2\pmod 4$ and $j_k\equiv 0\pmod 4$.

Let $F$ be the number of terms where $i_k\equiv 2\pmod 4$ and $j_k\equiv 1\pmod 4$.

Let $G$ be the number of terms where $i_k\equiv 2\pmod 4$ and $j_k\equiv 2\pmod 4$.

Let $H$ be the number of terms where $i_k\equiv 2\pmod 4$ and $j_k\equiv 3\pmod 4$.

Let $I$ be the number of terms where $i_k\equiv 3\pmod 4$ and $j_k\equiv 0\pmod 4$.

Let $J$ be the number of terms where $i_k\equiv 3\pmod 4$ and $j_k\equiv 1\pmod 4$.

Let $K$ be the number of terms where $i_k\equiv 3\pmod 4$ and $j_k\equiv 2\pmod 4$.

Let $L$ be the number of terms where $i_k\equiv 3\pmod 4$ and $j_k\equiv 3\pmod 4$.

We have $$0=h(-1)=-2A+2B-2C+2D-2I+2J-2K+2L$$ which implies $$0=-A+B-C+D-I+J-K+L\tag2$$

Also, we have $$\begin{align}0&=h(i) \\\\&=A(i-1)+Bi(i-1)+Ci^2(i-1)+Di^3(i-1) \\&\qquad +E(i^2-1)+Fi(i^2-1)+Gi^2(i^2-1)+Hi^3(i^2-1) \\&\qquad +I(i^3-1)+Ji(i^3-1)+Ki^2(i^3-1)+Li^3(i^3-1) \\\\&=A(i-1)+B(-1-i)+C(-i+1)+D(i+1) \\&\qquad -2E-2Fi+2G+2Hi \\&\qquad +I(-i-1)+J(-i+1)+K(i+1)+L(i-1) \\\\&=(A-B-C+D-2F+2H-I-J+K+L)i \\&\qquad -A-B+C+D-2E+2G-I+J+K-L\end{align}$$ which implies $$A-B-C+D-2F+2H-I-J+K+L=0\tag3$$ $$-A-B+C+D-2E+2G-I+J+K-L=0\tag4$$

From $(2)(3)(4)$, we get $$\begin{align}\sum\limits_{k=1}^m i_k&\equiv A+B+C+D+2(E+F+G+H)+3(I+J+K+L)\pmod 4 \\\\&=A+B+C+D+2(E+F+G+H)+3(I+J+K+L) \\&\qquad -A+B-C+D-I+J-K+L \\&\qquad +A-B-C+D-2F+2H-I-J+K+L \\&\qquad -A-B+C+D-2E+2G-I+J+K-L\pmod 4 \\\\&\equiv 4(D+G+H+K)\pmod 4 \\\\&\equiv 0\pmod 4.\ \blacksquare\end{align}$$