Exercise 2.8.12 (The congruence $x^n \equiv a \pmod p$ has a unique solution if $(n,p-1) = 1$)

Proof. Consider a primitive root $g$ modulo $p$. By hypothesis $a\not\equiv 0(\mathit{mod}p)$, thus $a\equiv g^b(\mathit{mod}p)$ for some integer $b$. Since $x^n\equiv a(\mathit{mod}p)$, then $x\not\equiv 0(\mathit{mod}p)$, so $x\equiv g^y$ for some integer $y$, where $0\le y<p-1$. Then

Since $n\wedge (p-1)=1$, this last congruence has exactly one solution modulo $p-1$. Indeed, if $m$ is an inverse of $n$ modulo $p-1$, i.e. $\mathit{mn}\equiv 1(\mathit{mod}p-1)$, then

There is a unique $y_0\in [[0,p-1[[$ such that $y_0\equiv \mathit{mb}(\mathit{mod}p-1)$, and so $y=y_0$. Therefore

where $y_0$ is the unique solution of $y_0\equiv \mathit{mb}(\mathit{mod}p-1),0\le y_0<p-1$.

If $p$ is a prime such that $a\wedge p=1$ and $n\wedge (p-1)=1$, then $x^n\equiv a(\mathit{mod}p)$ has exactly one solution.

(Note that $x^n\equiv 0(\mathit{mod}p)$ has also a unique solution $x\equiv 0(\mathit{mod}p)$, so we can forget the condition $a\wedge p=1$.) □