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$.

  • $\begingroup$ 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... $\endgroup$ – lulu Sep 15 '16 at 1:41
  • $\begingroup$ @lulu Why does the $\{ar_i\}$ form a subset of the residue list? $\endgroup$ – user42912 Sep 15 '16 at 1:43
  • $\begingroup$ Because each $ar_i$ is a non-zero residue and the residue list is the list of all such. $\endgroup$ – lulu Sep 15 '16 at 1:46
  • $\begingroup$ 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). $\endgroup$ – 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.