Exercise 2.8.11 (Squares of $(\mathbb{Z}/ 17\mathbb{Z})^*$)

Question

Using the data in the preceding problem, decide which of the congruences $x^2 \equiv 1, x^2 \equiv 2,x^2\equiv 3,\ldots,x^2 \equiv 16 \pmod{17}$, have solutions.

Richard Ganaye · Accepted Answer

ewcommand{\Z}{\mathbb{Z}}

\begin{proof} As in problem 8, we use the generator $g = \overline{3}$ of $(\Z/17\Z)^*$.

Consider the congruence $x^2 \equiv a \pmod{17}$, where $1\leq a \leq 16$.

Since $\overline{x}$ and $\overline{a}$ are in $(\Z/17\Z)^*$, we can write 
$$\overline{x} = g^y,\ 0 \leq y \leq 15,\qquad \overline{a} = g^b,\ 0 \leq b \leq 15.$$
Then
\begin{align*}
x^2 \equiv a \pmod{17} &\iff \overline{x}^2 = \overline{a}\
&\iff g^{2y} = g^b\
&\iff g^{2y-b} = \overline{1}\
&\iff 16 \mid 2y - b \qquad \qquad (	ext{the order of $g$ is $16$})\
&\iff 2y \equiv b \pmod {16}.\
\end{align*}
The last congruence $2y \equiv b \pmod {16}$ shows that $b$ is even.

Conversely, if $b$ is even, then $b = 2c$, where $0 \leq c \leq 7$. Then
\begin{align*}
x^2 \equiv a \pmod{17} &\iff 2y \equiv 2c \pmod {16}\
&\iff y \equiv c \pmod 8\
&\iff y = c 	ext{ or } y = 8 + c\qquad  \qquad (	ext{since }0 \leq y \leq 15)\
&\iff \overline{x}= g^c 	ext{ or } \overline{x} = - g^c \qquad \qquad (	ext{since } g^8 = -\overline{1})\
&\iff x \equiv 3^c 	ext{ or } x \equiv - 3^c \pmod{17}.
\end{align*}
To summarize, the congruence $x^2 \equiv a \pmod{17}$ has a solution if and only if $a = 3^{2c}$, where $0 \leq c \leq 7$.
\begin{align*}
\exists x \in \Z,\ x^2 \equiv a \pmod{17} &\iff a \equiv 3^0, 3^2,3^4,3^6,3^8,3^{10},3^{12},3^{14} \pmod{17}\
&\iff a \in \{1, 9, 13, 15, 16, 8, 4, 2\}
\end{align*}
(See the data of Problem 10.)
\end{proof}

Exercise 2.8.11 (Squares of $(\mathbb{Z}/ 17\mathbb{Z})^*$)

Answers

Comments

Exercise 2.8.11 (Squares of $(\mathbb{Z}/ 17\mathbb{Z})^*$)

Answers

Comments

Add answer