Let \((a, m) = 1\) and let the set \(\{r_1 , \ldots , r_k \}\) be a reduced residue system mod \(m\) where \(k = \phi(m)\). According to this lemma, \(\{ar_1 , \ldots , ar_k \}\) would also be a reduced residue system. Since \(\{r_1 , \ldots , r_k \}\) and \(\{ar_1 , \ldots , ar_k \}\) both contain the same residue (modulo \(m\)):
$$\begin{align} (ar_1 \ldots ar_k) &≡ (r_1\ldots r_k) \mod m \\ a^{\phi(m)}(r_1r_2 \ldots r_k) &≡ (r_1r_2 \ldots r_k) \end{align}$$
If \((a, m) = 1\), then \((a^k, m) = 1\). If \((a^{\phi(m)}, m) = 1\) and \((r_1r_2 \ldots r_k) (a^{\phi(m)}) ≡ (r_1r_2 \ldots r_k) (1)\), then, according to this:
$$a^{\phi(m)} ≡ 1 \mod \left( \frac{m}{(r_1r_2 \ldots r_k, m)} \right) $$
If \((r_i, m) = 1\) and \((r_j, m) = 1\), then, according to this, \((r_ir_j, m) = 1\). Using this line of reasoning repeatedly, we can say \((r_1r_2 \ldots r_k,m) = 1\):
$$a^{\phi(m)} ≡ 1 \mod \left( \frac{m}{(r_1r_2 \ldots r_k, m)} \right) \implies a^{\phi(m)} ≡ 1 \mod m $$