Exercise 2.8.8 (Number of solutions of $x^{12} \equiv 16 \pmod {17}$, and other congruences)

Proof.

(a)

Here $p=17,n=12$, and $n\wedge p-1=12\wedge 16=4$. Moreover $16^{(p-1)∕4}\equiv {(-1)}^4=1$. By Theorem 2.37, there are $4$ solutions to the congruence $x^{12}\equiv 16(\mathit{mod}17)$.

More explicitly, $g=\bar{3}$ is a generator of $\mathbb{Z}∕17\mathbb{Z}$ (where we write $\bar{x}={[x]}_{17}\in \mathbb{Z}∕17\mathbb{Z}$ the class of $x\in \mathbb{Z}$), and $\overline{16}=g^8$. We can write $\bar{x}=g^y$, where $0\le y\le 15$. Then

$$\begin{array}{llll}\hfill x^{12}\equiv 16(\mathit{mod}17)& ⟺{\bar{x}}^{12}=\overline{16}& \hfill & \\ \hfill & ⟺g^{12y}=g^8& \hfill & \\ \hfill & ⟺g^{12y-8}=1& \hfill & \\ \hfill & ⟺16\mid 12y-8& \hfill & \\ \hfill & ⟺12y\equiv 8(\mathit{mod}16)& \hfill & \\ \hfill & ⟺3y\equiv 2(\mathit{mod}4)& \hfill & \\ \hfill & ⟺y\equiv 2(\mathit{mod}4)& \hfill & \\ \hfill & ⟺\exists <!--\; FUNCTION\; APPLICATION\; -->k\in \mathbb{Z},y=2+4k.& \hfill & \end{array}$$

Since $0\le y\le 15$, the values $k=0,1,2,3$ give all solutions:

$$\begin{array}{llll}\hfill x^{12}\equiv 16(\mathit{mod}17)& ⟺\bar{x}\in \{g^2,g^6,g^{10},g^{14}\}& \hfill & \\ \hfill & ⟺\bar{x}\in \{9,15,8,2\}& \hfill & \\ \hfill & ⟺x\equiv 2,8,9,15(\mathit{mod}17).& \hfill & \end{array}$$

(b)

Here $n\wedge (p-1)=48\wedge 16=16$. Since $9^{(p-1)∕16}=9\not\equiv 1(\mathit{mod}17)$, the congruence $x^{48}\equiv 9(\mathit{mod}17)$ has no solution by Theorem 2.37.

(More quickly, by Fermat’s theorem, $x^{16}\equiv 1(\mathit{mod}17)$, if $x\not\equiv 0(\mathit{mod}17)$. Therefore $x^{48}\equiv 0\text{ or }1(\mathit{mod}17)$, thus $x^{48}\not\equiv 9(\mathit{mod}17)$, for all $x\in \mathbb{Z}$.)

(c)

Here $n\wedge (p-1)=20\wedge 16=4$, and $13^4\equiv 1(\mathit{mod}17)$, thus the congruence $x^{20}\equiv 13(\mathit{mod}17)$ has $4$ solutions.

As in part (a),

$$x^{20}\equiv 13(\mathit{mod}17)⟺x\equiv 3,5,12,14(mod17).$$

(d)

Here $n\wedge (p-1)=11\wedge 16=1$, and $13^{(p-1)∕1}\equiv 1(\mathit{mod}17)$, thus the congruence $x^{11}\equiv 9(\mathit{mod}17)$ has exactly one solution.

Since $15^{11}\equiv 9(\mathit{mod}17)$,

$$\begin{array}{lll}\hfill x^{11}\equiv 9(\mathit{mod}17)⟺x\equiv 15(mod17).& & \hfill \text{(1)}\end{array}$$

Alternatively, the Bézout’s algorithm gives $3\times 11-2\times 16=1$, thus

$$x^{11}\equiv 9(\mathit{mod}17)\Rightarrow \bar{x}={({\bar{x}}^{11})}^3\cdot {({\bar{x}}^{16})}^{-2}={\bar{9}}^3=\overline{15}\Rightarrow x\equiv 15(mod17),$$

and conversely, $15^{11}\equiv 9(\mathit{mod}17)$. This is another proof of (1).