Let $2 \pmod p$ where $p$ is an odd prime have order $rs$ where $s > 1$. If $2^r \not \equiv 1 \pmod p$, prove that
$$ 2^{r(s - 1)} + 2^{r(s - 2)} + 2^{r(s - 3)} + \ldots + 2^r + 1 \equiv 0 \pmod p $$
Hint: $2^{rs} - 1 = (2^r -1) (2^{r(s - 1)} + 2^{r(s - 2)} + 2^{r(s - 3)} + \ldots + 2^r + 1)$
We're given $rs$ is the order of $2 \pmod p$. This means
$$ 2^{rs} \equiv 1 \pmod p $$
That is
$$ 2^{rs} -1 \equiv 0 \pmod p $$
Using the hint gives us
$$ \bigl (2^r -1 \bigr ) \bigl (2^{r(s - 1)} + 2^{r(s - 2)} + 2^{r(s - 3)} + \ldots + 2^r + 1 \bigr ) \equiv 0 \pmod p $$
Since $p$ is prime, by Proposition (3.14), either or both of the following is true
- $2^r-1 \equiv 0 \pmod p$
- $2^{r(s - 1)} + 2^{r(s - 2)} + 2^{r(s - 3)} + \ldots + 2^r + 1 \equiv 0 \pmod p$.
If $2^r \not \equiv 1 \pmod p$ then $(2^r-1) \not \equiv 0 \pmod p$. This rules out the first option above, leaving only the second as true.
That is,
$$ 2^{r(s - 1)} + 2^{r(s - 2)} + 2^{r(s - 3)} + \ldots + 2^r + 1 \equiv 0 \pmod p$$
Note: We don't need to assume $2^r \not \equiv 1 \pmod p$. We're given $s>1$ which means $rs > r$, and since $rs$ is the order of $2$ modulo $p$, we can't have $r<rs$ as order, that is we can't have $2^r \equiv 1 \pmod p$.