Can Lagrange's Theorem for algebraic structure apply here?

Question

For a positive integer $n$ let $Φ(n)$ denote the number of elements $r∈\mathbb Z_n$ such that $\gcd(r,n)=1$. Show $Φ(mn)=Φ(m)Φ(n)$ for all $m, n∈\mathbb N$ such that $\gcd(m,n)=1$.

The only thing I can come up with when seeing this question is that those r's are generators of the ring they are in...

Intuitively, I think I should apply Lagrange's Theorem, but I have no idea how to use it...

Answer 1

A very group theoretic way to prove your claim is outlined in the following:

1. Prove that for $n$ and $m$ co-prime, that is $\gcd(n,m)=1$, you have an isomorphism $\mathbb Z_{nm} \cong \mathbb Z_{n}\times \mathbb Z_{m}$ (where $\times$ denote the direct product of groups).
2. Prove that the generators of $\mathbb Z_n \times \mathbb Z_m$ are exactly ordered pairs $(x,y)$ where $x$ is a generator of $\mathbb Z_n$ and $y$ is a generator of $\mathbb Z_m$.
3. Using your initial observation, namely that $\Phi(n)$ is the number of generators of $\mathbb Z_n$, and the point 1 conclude the claim that $\Phi(nm)=\Phi(n)\Phi(m)$.

Note that in order to prove this points you need to use only properties of cyclic groups (which usually are proved through Lagrange's theorem).

If you need additional hint feel free to ask.