Let \((a, m) = 1\) and let the set \(\{r_1 , \ldots , r_k \}\) be a reduced residue system mod \(m\) where \(k = \phi(m)\). Using this lemma, we can say that if \((r_i, m) = 1\) and \((a, m) = 1\), then \((ar_i, m) = 1\), this shows that \(ar_i\) is coprime to \(m\). Also, if we had \(ar_i ≡ ar_j \mod m\), then:
$$ m|ar_i - ar_j = a(r_i - r_j ) $$
If \((a, m) = 1\) then, according to this lemma, \(m|r_i - r_j\):
$$ m|r_i - r_j ⇒ r_i ≡ r_j \mod m $$
This cannot be true unless i = j. This shows all \(ar_i\) are distinct modulo \(m\), therefore \(\{ar_1 \ldots ar_k \}\) is also a reduced residue system.