Reduced residue system from complete residue system

Question

Where can I read a proof of the following result? Online or textbook preferably.

If $\Gamma = \{a_1, a_2, \ldots, a_m\}$ is a complete residue system modulo $m$, then $\{a_i \in \Gamma| g.c.d.(a_i, m) = 1\}$ is a reduced residue system modulo $m$.

Answer 1

The $a_i$ such that $\gcd(a_i,m)=1$ are all relatively prime to $m$. Now we need to show that if $0\le b\lt m$ and $\gcd(b,m)=1$, then $b\equiv a_i\pmod{m}$ for some $a_i$ such that $\gcd(a_i,m)=1$.

Because $\Gamma$ is a complete residue system, it follows that $b\equiv a_i\pmod{m}$ for some unique $a_i\in \Gamma$. We show that $\gcd(a_i,m)=1$. Suppose to the contrary that some $d\gt 1$ divides both $a_i$ and $m$. Since $b\equiv a_i\pmod{m}$, we have $m\mid (b-a_i)$, and therefore $d\mid (b-a_i)$. Thus $d\mid (b-a_i)+a_i$, and therefore $d\mid b$. This contradicts the fact that $\gcd(b,m)=1$.