# Help in this proof of Niven, Zuckerman, Montgomery's number theory book

I'm reading Niven, Zuckerman, Montgomery's number theory book and on page 51 they state this theorem:

Theorem 2.6: Let $(a,m)=1$. Let $r_1,r_2,\ldots, r_n$ be a complete, or a reduced, residue system modulo $m$. Then $ar_1,ar_2,\ldots,ar_n$ is a complete, or a reduced, residue system, respectively, modulo $m$.

Proof: If $(r_i,m)=1$, then $(ar_i,m)=1$ by theorem 1.8. There are the same number of $ar_1,ar_2,\ldots,ar_n$ as of $r_1,r_2,\ldots,r_n$. Therefore we need only show that $ar_i\not\equiv ar_j\pmod m$ if $i\neq j$. But thereom 2.3, part 2, shows that $ar_i\equiv ar_j \pmod m$ implies $r_i\equiv r_j \pmod m$ and hence $i=j$

I didn't understand why every integer is a residue of some of $ar_1,\ldots,ar_j$ modulo $m$.

• Well, the $\{ar_i\}$ form a subset of the residue list and the first argument shows that this subset has the same size as the full list so... – lulu Sep 15 '16 at 1:41
• @lulu Why does the $\{ar_i\}$ form a subset of the residue list? – user42912 Sep 15 '16 at 1:43
• Because each $ar_i$ is a non-zero residue and the residue list is the list of all such. – lulu Sep 15 '16 at 1:46
• Here, I'm thinking of each residue as an equivalence class. If you prefer to think about them as actual integers then it's better to say that there is an injection from $\{ar_i\}$ into the list $\{r_i\}$ given by congruence (each $ar_i$ is mapped to whichever $r_j$ it is congruent to (we were assured the original list was complete so there has to be one and only one such). – lulu Sep 15 '16 at 1:50

Note that for each $i$, there exists a unique $j$ such that $ar_i\equiv r_j\pmod{m}$. Let's write $f(i)$ for this unique $j$ (depending on $i$). The argument given shows that $f$ is an injective function from $\{1,\dots,n\}$ to $\{1,\dots,n\}$, since $ar_i\not\equiv ar_j\pmod{m}$ if $i\neq j$. Any injective function from a finite set to itself is also surjective, so $f$ is surjective. This means that for any $j$, there exists an $i$ such that $ar_i\equiv r_j\pmod{m}$. For any integer $x$, there is by assumption some $j$ such that $x\equiv r_j\pmod{m}$, and hence some $i$ such that $x\equiv ar_i\pmod{m}$.