Exercise 2.8.9 ($3$ is a primitive root of $17$)

Proof. Since $3^4=9^2=81=4\times 17+13\equiv -4(\mathit{mod}17)$, $3^8\equiv {(-4)}^2=16\equiv -1(\mathit{mod}17)$, thus

Let $r$ be the order of $3$ modulo $17$. Since $3^{16}\equiv 1(\mathit{mod}17)$, and $3^8\not\equiv 1(\mathit{mod}17)$, $r\mid 2^4$ and $r\nmid 2^3$, therefore $r=16$. So $3$ is a primitive root modulo $17$. □