# Given a prime $p$ and a positive integer $a \not \equiv 0,1 \pmod p$, show that S = $\sum^{p-1}_{i=1} a^i \equiv 0 \pmod p$

The origin of this question is actually a different question:

• Show that all primes except 2 and 5 divide infinitely many elements of $$B :=\{1,11,111,1111,\cdots\}$$.

It's relatively straightforward to see that the $$k$$th element of $$B$$ is:

$$b_k = \sum^{k}_{i=0} 10^i$$

If we can find an infinite set $$\{k_1, k_2, \cdots\}$$, probably evenly spaced, where $$p \mid b_k$$ and so $$b_k \equiv 0 \pmod p$$, and it works for all $$p$$, then we have a proof.

It's always nice to look at the low-hanging fruit to get your bearings. The solutions for $$2, 3, 5, 11$$ are nearly trivial but show us some patterns:

• Since for all elements $$b_k \equiv 1 \pmod{10}$$, $$2$$ and $$5$$ can never divide any elements in the set.
• By the typical $$3$$s divisibility test, since $$10 \equiv 1 \pmod 3$$, we're adding $$1$$ regularly, so every third element is divisible by $$3$$.
• Every second element is divisible by $$11$$ just by inspection: $$11 = (11 \cdot 1), 1111 = (11 \cdot 101), 111111 = (11 \cdot 10101),$$ etc.

Looking at modulo $$7$$, I realized that $$10 \equiv 3 \pmod 7$$ is a primitive root, and so $$\{10^1, 10^2, \cdots, 10^{p-1} \} = \{1,2,\cdots, 6\}$$. And their sum is divisible by $$7$$, since it's the sum of consecutive integers, i.e., $$S = 7 \cdot \frac{7-1}{2} \equiv 21 \equiv 0 \pmod 7$$. Because the cycle length is $$6$$, every $$6$$th element of $$B$$ is divisible by $$7$$. The divisibility question is now a summation question... for which I still haven't yet determined a proof.

This line of thinking led me to consider numbers other than $$10$$, leading to the more generalized question asked in the title, i.e.,

$$S = \sum^{p-1}_{i=1} a^i \overset{?} \equiv 0 \pmod p$$

There are a number of "easy" cases:

1. If $$a \equiv 1 \pmod p$$, then $$S \equiv 1 \pmod p$$, and the case must be excluded.
2. If $$a \equiv p-1 \equiv -1 \pmod p$$, then every odd power is $$-1 \pmod p$$ and every even power is $$1 \pmod p$$. Since the total number of powers is even, the final sum is $$S \equiv 0 \pmod p$$.
3. If $$a$$ is a primitive root modulo $$p$$, then every residue appears exactly once in the sum, so $$S$$ is the sum of consecutive integers: $$S = (\frac{p-1}{2})p \equiv 0 \pmod p$$.

But what about the residues that are not primitive roots? I've found a few partial answers that lead to more new questions. For instance, if $$a \not \equiv -1, 0, 1 \pmod p$$, and is not a primitive root modulo $$p$$, it still "generates" a--subgroup? subring? I'm uncertain of the terminology--in any case, a subset of $$\mathbb{Z} / p \mathbb{Z}$$ that is also closed under multiplication.

For instance, modulo $$13$$, there are four primitive roots: $$\{2, 6, 7, 11\}$$. But additionally:

• $$a = 3$$ or $$a = 9$$ "generates" the subset $$\{1,3,9\}$$
• $$a = 4$$ or $$a = 10$$ "generates" the subset $$\{1,3,4,9,10,12\}$$
• $$a = 5$$ or $$a = 8$$ "generates" the subset $$\{1,5,8,12\}$$

And each of those subsets

• is closed under multiplication modulo $$p$$
• has (by definition) $$\text{ord}_p(a)$$ elements
• adds up to $$0 \pmod p$$. Because $$\text{ord}_p(a) \mid p-1$$, the sum $$S$$ will run through the same elements $$\frac{p-1}{\text{ord}_p(a)}$$ times. This means the sum will still be $$S \equiv 0 \pmod p$$.

I've only determined these empirically, alas, and so I come to mathSE hoping to find an actual method for a proof. (Or a link to somewhere that it's been proven.)

• You have a good start, but I'm sure this is a duplicate. Hint: By Little Fermat you know that $a^p\equiv a\pmod p$. This implies that $a S\equiv S$, because $aS$ has the same terms, only shifted cyclically. Therefore $(a-1)S$ is divisible by $p$. Sep 17, 2021 at 2:55
• For example in one of your example cases, $a=5, p=13,$ you have $S\equiv 1+5+12+8$ implying that $5S\equiv5+12+8+1$. Sep 17, 2021 at 3:00
• If everything else fails, use the formula for a geometric sum, boring as it is :-) Sep 17, 2021 at 3:09
• THis is not the most informative way but notice that $[\sum_{i=1}^{p-1}a^i](a-1) = a^p-a$. And by FLT we have $a^p \equiv a \pmod p$ and $1- p \equiv 1 \pmod p$ so $\sum_{i=1}^{p-1}a^i\equiv (1-p)\sum_{i=1}^{p-1}a^i\equiv a- a^p \equiv 0\pmod p$. (Feels like we are cheating, doesn't it) Your idea is good and will work. But you have to iron out the details Sep 17, 2021 at 6:29
• @JyrkiLahtonen OK, now I feel a bit foolish, because the geometric sum is right there under our noses. There's no leading coefficient, and we have skipped $a^0 = 1$, so $$S \equiv \frac{1-a^p}{1-a} - 1 \equiv \frac{1-a}{1-a} - 1 \equiv 0 \pmod p$$ ...and that satisfies the proof. Always learning! Sep 18, 2021 at 1:10

We have $$S = \sum^{p-1}_{i=1} a^i = a\sum^{p-2}_{i=0} a^i = \frac a{a-1}(a-1)\sum^{p-2}_{i=0} a^i = \frac a{a-1}(a^{p-1}-1) = \frac {a^p-a}{a-1}$$ where the division by $$a-1$$ works because $$a\not\equiv 1$$.
Due to Fermat's little theorem, $$a^p\equiv a$$ because $$p$$ is prime, which proves your assertion for all $$a\not\equiv 1$$.
• As for your addendum: Let $n=p^2$ and $a=p$ for some prime $p$ to see it's not true. Sep 18, 2021 at 12:30