Exercise 5.20

Proof. From Ex. 5.19 we know that there exist exactly $\varphi (D)∕2$ integers $a_i$ between $1$ and $D$ such that $a_i\wedge D=1$ and $(a_i∕D)=1$. So $\{\overline{a_1},\dots ,\overline{a_{\varphi (D)∕2}}\}$ is the set of all $\bar{a}\in U(\mathbb{Z}∕\mathit{D\mathbb{Z}})$ such that $(a∕D)=1$.

Let $D=p_1{p}_2\cdots p_k$, with distinct $p_i$, and $p$ a prime number, $p\equiv 1(\mathit{mod}4),p\notin \{p_1,\dots ,p_k\}$ (so $p=4k+1,k\in \mathbb{N}$).

( $\Leftarrow$) Suppose that $p\equiv a_i$ for some $i,1\le i\le \varphi (D)∕2$, then $(p∕D)=(a_i∕D)=1$, so (Prop. 5.2.2)

( $\Rightarrow$) Suppose that $D$ is a quadratic residue modulo $p$. Then $(D∕p)=1$, so

Thus $\bar{p}\in \{\overline{a_1},\dots ,\overline{a_{\varphi (D)∕2}}\}$ since $\{\overline{a_1},\dots ,\overline{a_{\varphi (D)∕2}}\}$ is the set of all $\bar{a}\in U(\mathbb{Z}∕\mathit{D\mathbb{Z}})$ such that $(a∕D)=1$. Consequently $p\equiv a_i(\mathit{mod}D)$ for some $i$. □