Ich bezeichne mit \(Z_n\) den Restklassenring \(\mathbb{Z}/n\mathbb{Z}\).
Die prime Restklassengruppe mod \(n\) besteht aus den invertierbaren
Elementen von \(Z_n\). Das ist die Einheitengruppe \(Z_n^*\) von \(Z_n\).
Sind nun \(m\) und \(n\) teilerfremd, so besagt der chinesische
Restsatz, dass \(Z_{mn}\cong Z_m\times Z_n\) gilt. Für die Einbheitengruppen
ergibt sich daraus \(Z_{mn}^*\cong Z_m^* \times Z_n^*\).
Da \(\varphi(n)=|Z_n^*|\) ist, ergibt sich
\(\varphi(mn)=|Z_{mn}^*|=|Z_m^*|\cdot |Z_n^*|=\varphi(m)\cdot \varphi(n)\).
