Exercise 3.6

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 an integer $n > 0$ be given. A set of integers $a_1, \ldots, a_{\phi(n)}$ is called a reduced residue system modulo $n$ if they are pairwise incongruent modulo $n$ and $(a_i, n) = 1$ for all $i$. If $(a, n) = 1$, prove that $aa_1 , aa_2, \ldots, aa_{\phi(n)}$ is again a reduced residue system modulo $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}
Let  $a_1, \ldots, a_{\phi(n)}$ a reduced residue system modulo $n$.

$\bullet$ As $a\wedge n = 1$ and $a_i \wedge n=1, \ i=1,2,\ldots,\phi(n)$, then $aa_i \wedge n=1$.

$\bullet$ As $a\wedge n = 1$, there exists $a' \in \Z$ such that $aa'\equiv 1 \pmod n$. then
$$a a_i \equiv a a_j \Rightarrow a'aa_i \equiv a'aa_j \pmod n \Rightarrow a_i \equiv a_j \pmod n.$$
So $i
eq j \Rightarrow a_i 
ot \equiv a_j \Rightarrow a a_i 
ot \equiv a a_j$ :

$aa_1, \ldots, aa_{\phi(n)}$ a reduced residue system modulo $n$.

\medskip

Note that $\{a_1,a_2,\ldots, a_{\phi(n)}\}$ is a reduced residue system modulo $n$  if and only if $\{\overline{a_1},\overline{a_2},\ldots,\overline{a_{\phi(n)}}\} = U(\Z/n\Z)$.
\end{proof}

Exercise 3.6

Answers

Comments

Exercise 3.6

Answers

Comments

Add answer