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$

Question

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.)

Answer 1

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$.