Let $a \not \equiv 1 \pmod p$ and $a \mod p$ have order $k$. Prove that
$$ a^{k−1} + a^{k−2} + a^{k−3} + \ldots + 1 \equiv 0 \pmod p $$
where $p$ is prime.
We use the following algebraic identity:
$$ a^{k} - 1 = (a -1) (a^{k - 1} + a^{k - 2} + a^{k - 3} + \ldots + a + 1) $$
Since the order of $a$ modulo $p$ is $k$, we have $a^k \equiv 1 \pmod p $, which gives us
$$ \begin{align} a^k -1 & \equiv 0 \pmod p \\ \\ (a -1) (a^{k - 1} + a^{k - 2} + a^{k - 3} + \ldots + a + 1) \equiv 0 \pmod p \end{align}$$
Since $p$ is prime, Proposition (3.14) tells us that at least of the following is true
- $a -1 \equiv 0 \pmod p$
- $a^{k - 1} + a^{k - 2} + a^{k - 3} + \ldots + a + 1 \equiv 0 \pmod p$
We're given $a \not \equiv 1 \pmod p$, which is $a -1 \not \equiv 0 \pmod p$. This rules out the first option, leaving only the second as true.
That is,
$$ a^{k - 1} + a^{k - 2} + a^{k - 3} + \ldots + a + 1 \equiv 0 \pmod p $$