Here is an indirect solution - a solution that doesn't use any specific primitive root. I think a better solution exists, but I would still like to post it because it gives a different perspective.

The solutions $1$ and $m-1$ are obviously always solutions. So the difficulty is proving there aren't any more.

By the primitive root theorem, the possibilities for $m$ are $m=2$, $m=4$, $m=p^k$, or $m=2p^k$ where $p$ is an odd prime and $k\ge 1$.

For $m=2$ we actually have $1=m-1$, and there is a *unique* square root of $1$.

For $m=4$ you may check directly that the claim holds, just by calculating.

For $m=p^k$, we prove by induction on $k$. For $k=1$ there are no zero divisors, so $(x-1)(x+1)=0$ implies $x-1=0$ or $x+1=0$. For $k>1$, assuming there are exactly two solutions modulo $p^{k-1}$, we use Hensel's lemma to claim that these lift to exactly two solutions modulo $p^k$.

For $m=2p^k$ we use the Chinese remainder theorem to combine the two solutions modulo $p^k$ with the unique solution modulo $2$ to get two solutions modulo $m$.

$$\begin{array}{rcl}
x^2 &\equiv& 1 \pmod{15} \\
(x-1)(x+1) &\equiv& 0 \pmod{15}
\end{array}$$

So, $x=1$, $x=-1$, $x=4$, or $x=-4$.

## Best Answer

We know that $2^{28} \equiv 1 \bmod 29$, i.e. $16^7 \equiv 1 \bmod 29$. However we can also conclude from this that:

$16^{14},16^{21},16^{28},16^{35},16^{42},16^{49} \equiv 1 \bmod 29$.

So $16^2, 16^3, 16^4, 16^5, 16^6, 16^7$ are the other $6$ solutions.

Alternatively: we know every $x\in\mathbb{Z}/29\mathbb{Z}$ can be written as $x=2^k$ for some $k$.

To satisfy $x^7 \equiv 1 \bmod 29$ we require $2^{7k} \equiv 1 \bmod 29$. But since $2$ is a primitive root mod $29$ this means that $7k \equiv 0 \bmod 28$, i.e. $k \equiv 0 \bmod 4$ so we may take $k=0,4,8,12,16,20,24$ (after this the powers of $2$ repeat).