Exercise 2.8.10 (Solutions of congruences of Problem 8)

Proof. This array gives the powers of the primitive root $3$ modulo $17$:

With Sage:

sage: a = Mod(3, 17)
sage: [a^k for k in range(1,17)]
[3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1]

(a)

Write $\bar{x}=g^y$ where $g=\bar{3}\in \mathbb{Z}∕17\mathbb{Z}$, and $0\le y\le 15$. We read in the array that $16\equiv 3^8(\mathit{mod}17)$. Then (as in the solution of Problem 8) $$\begin{array}{llll}\hfill x^{12}\equiv 16(\mathit{mod}17)& ⟺g^{12y}=g^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 & ⟺y\in \{2,6,10,14\}(0\le y\le 15)& \hfill & \\ \hfill & ⟺x\in \{\bar{2},\bar{8},\bar{9},\overline{17}\}& \hfill & \\ \hfill & ⟺x\equiv 2,8,9,15(\mathit{mod}17).& \hfill & \end{array}$$

(b)

Similarly, with the same notations, $$\begin{array}{llll}\hfill x^{48}\equiv 9(\mathit{mod}17)& ⟺g^{48y}=g^2& \hfill & \\ \hfill & ⟺48y\equiv 2(\mathit{mod}16).& \hfill & \end{array}$$

This last congruence has no solution, because $16\mid 48$, but $16\nmid 2$.

(c)

Here the array gives $13\equiv 3^4(\mathit{mod}17)$. Thus $$\begin{array}{llll}\hfill x^{20}\equiv 13& ⟺g^{20y}=g^4& \hfill & \\ \hfill & ⟺20y\equiv 4(\mathit{mod}16)& \hfill & \\ \hfill & ⟺5y\equiv 1(\mathit{mod}4)& \hfill & \\ \hfill & ⟺y\equiv 1(\mathit{mod}4)& \hfill & \\ \hfill & ⟺y\in \{1,5,9,13\}(0\le y\le 15)& \hfill & \\ \hfill & ⟺x\equiv 3,5,14,12(\mathit{mod}17).& \hfill & \end{array}$$

(d)

Since $9=3^2$, $$\begin{array}{llll}\hfill x^{11}\equiv 9(\mathit{mod}17)& ⟺g^{11y}=g^2& \hfill & \\ \hfill & ⟺11y\equiv 2(\mathit{mod}16)& \hfill & \\ \hfill & ⟺y\equiv 6(\mathit{mod}16)(\text{using }3\times 11-2\times 16=1)& \hfill & \\ \hfill & ⟺y=6(0\le y\le 15)& \hfill & \\ \hfill & ⟺x\equiv 3^6\equiv 15(\mathit{mod}17).& \hfill & \end{array}$$