4
$\begingroup$

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

$\endgroup$
5
  • 3
    $\begingroup$ 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$. $\endgroup$ Commented Sep 17, 2021 at 2:55
  • $\begingroup$ 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$. $\endgroup$ Commented Sep 17, 2021 at 3:00
  • 7
    $\begingroup$ If everything else fails, use the formula for a geometric sum, boring as it is :-) $\endgroup$ Commented Sep 17, 2021 at 3:09
  • $\begingroup$ 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 $\endgroup$
    – fleablood
    Commented Sep 17, 2021 at 6:29
  • 1
    $\begingroup$ @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! $\endgroup$ Commented Sep 18, 2021 at 1:10

1 Answer 1

1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ As for your addendum: Let $n=p^2$ and $a=p$ for some prime $p$ to see it's not true. $\endgroup$
    – Mastrem
    Commented Sep 18, 2021 at 12:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .