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:
- If $a \equiv 1 \pmod p$, then $S \equiv 1 \pmod p$, and the case must be excluded.
- 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$.
- 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.)