proof that Euler $\phi$ function is multiplicative

Suppose that $t=mn$ where $m,n$ are coprime. The Chinese remainder theorem (http://planetmath.org/ChineseRemainderTheorem) states that $\gcd (a,t)=1$ if and only if $\gcd (a,m)=1$ and $\gcd (a,n)=1$.

In other words, there is a bijective correspondence between these two sets:

• $\{a:a\equiv 1(modt)\}$

• $\{a:a\equiv 1(modm)\text{ and }a\equiv 1(modn)\}$

Now the number of positive integers not greater than $t$ and coprime with $t$ is precisely $\phi (t)$, but it is also the number of pairs $(u,v)$, where $u$ not greater than $m$ and coprime with $m$, and $v$ not greater than $n$ and coprime with $n$. Thus, $\phi (mn)=\phi (m)\phi (n)$.