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 $\mathrm{gcd}(a,t)=1$ if and only if $\mathrm{gcd}(a,m)=1$ and $\mathrm{gcd}(a,n)=1$.
In other words, there is a bijective^{} correspondence between these two sets:

•
$\{a:a\equiv 1\phantom{\rule{veryverythickmathspace}{0ex}}(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)$.
Title  proof that Euler $\phi $ function is multiplicative 

Canonical name  ProofThatEulervarphiFunctionIsMultiplicative 
Date of creation  20130322 15:03:40 
Last modified on  20130322 15:03:40 
Owner  Wkbj79 (1863) 
Last modified by  Wkbj79 (1863) 
Numerical id  12 
Author  Wkbj79 (1863) 
Entry type  Proof 
Classification  msc 11A25 
Related topic  EulerPhiFunction 
Related topic  MultiplicativeFunction 
Related topic  EulerPhifunction 