Proof. To show that each integer $a r_{j}$ is relatively prime to $n$, we assume that $\left(a r_{j}, n\right)>1$. Then, there is a prime divisor $p$ of $\left(a r_{j}, n\right)$. Hence, either $p \mid a$ or $p \mid r_{j}$. Thus, we either have $p \mid a$ and $p \mid n$, or $p \mid r_{j}$ and $p \mid n$. However, we cannot have both $p \mid r_{j}$ and $p \mid n$, since $r_{j}$ is a member of a reduced residue modulo $n$, and both $p \mid a$ and $p \mid n$ cannot hold since $(a, n)=1$. Hence, we can conclude that $a r_{j}$ and $n$ are relatively prime for $j=1,2, \ldots, \phi(n)$.

To demonstrate that no two $a r_{j}$ 's are congruent modulo $n$, we assume that $a r_{j} \equiv a r_{k}(\bmod n), \quad$ where $j$ and $k$ are distinct positive integers with $1 \leqslant j \leqslant \phi(n)$ and $1 \leqslant k \leqslant \phi(n)$. Since $(a, n)=1$, by Corollary 3.1 we see that $r_{j} \equiv r_{k}(\bmod n)$. This is a contradiction, since $r_{j}$ and $r_{k}$ come from the original set of reduced residues modulo $n$, so that $r_{j} \not \equiv r_{k}(\bmod n)$.