Exercise 3.11

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

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

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{
}{\mathrm{N}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

Let $a_1, \ldots, a_{\phi(n)}$ be a reduced residue system modulo $n$ and let $N$ be the number of solutions to $x^2 \equiv 1 \pmod n$. Prove that $a_1 \cdots a_{\phi(n)} \equiv (-1)^{N/2} \pmod n$.

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow} \def\gcro{\mbox{[\hspace{-.15em}[}} \def\dcro{\mbox{]\hspace{-.15em}]}} ewcommand{\D}{\mathrm{d}} ewcommand{\Q}{\mathbb{Q}} ewcommand{\Z}{\mathbb{Z}} ewcommand{\N}{\mathbb{N}} ewcommand{\R}{\mathbb{R}} ewcommand{\C}{\mathbb{C}} ewcommand{\F}{\mathbb{F}} ewcommand{ e}{\,\mathrm{Re}\,} ewcommand{\ord}{\mathrm{ord}} ewcommand{ }{\mathrm{N}} ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}} \begin{proof} If $n=2$, then $N=1$ and the result is false. So we suppose $n>2$. Let $H$ be the subset of $\Z/n\Z$ containing all $x \in \Z/n\Z$ such that $x^2=1$: $$H = \{x \in \Z/n\Z\ \vert \ x^2 = 1\}$$ (here $1 = \overline{1}$). Then $H \subset U(\Z/n\Z)$, $1 \in H e \varnothing$, and $$x \in H, y \in H \Rightarrow x^2 = y^2=1 \Rightarrow (xy^{-1})^2 = 1 \Rightarrow xy^{-1} \in H,$$ so $H$ is a subgroup of $(U(\Z/n\Z), imes)$, and $N = \mathrm{Card}\, H$. Each $x \in U(\Z/n\Z)$ such that $x ot \in H$ can be paired with its inverse $x^{-1}$, and $xx^{-1} = 1$, so $$P := \prod_{x \in U(\Z/n\Z)} x = \prod_{x\in H} \, x.$$ If $x \in H, -x \in H$. $\bullet$ If $n$ is odd, each $x = \overline{a}\in H (a\in \Z, 1\leq a \leq n-1)$ satisfies $-x eq x$: otherwise $2 a \equiv 0 \pmod n, 2a = k n, k \in \Z$ . As $0<2a = kn < 2n$, then $k=1$, and $n = 2a$ is even, in contradiction with the hypothesis. So each $x \in H$ can be paired with $-x$ in the product $P$, and $x(-x) = -1$, so $$P = \prod_{x\in H} \, x = (-1)^{N/2}.$$ $\bullet$ If $n$ is even, assume that some $x = \overline{a}\in H\ (a\in \Z, 1\leq a \leq n-1)$ satisfies $x = -x$, then $0 < a = k \frac{n}{2} < n$, so $a = \frac{n}{2}$, and $x = \overline{ \left(\frac{n}{2} ight)}$ is the only element in $\Z/n\Z$ such that $x = -x$. Then $\overline{2}x = \overline{0}$, and $x \in H$, so $\overline{2} x^2 = \overline{0}, \overline{2} = \overline{0}$. Since $n>2$, this is impossible, so $x eq -x$ for all $x \in H$, and $\prod_{x\in H} \, x = (-1)^{N/2}$. Conclusion: if $n>2$, $$\prod_{x \in U(\Z/n\Z)} x = (-1)^{N/2}.$$ If $a_1, \ldots, a_{\phi(n)}$ is a reduced residue system modulo $n$, then $\overline{ a_1 \cdots a_{\phi(n)}} = P = \prod_{x \in U(\Z/n\Z)} x = (-1)^{N/2}$, so $$a_1 \cdots a_{\phi(n)} \equiv (-1)^{N/2} \pmod n.$$ \end{proof}

Exercise 3.11

Answers

Comments

Exercise 3.11

Answers

Comments

Add answer