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)$.

Title	proof that Euler $\phi$ function is multiplicative
Canonical name	ProofThatEulervarphiFunctionIsMultiplicative
Date of creation	2013-03-22 15:03:40
Last modified on	2013-03-22 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