# proof that Euler $\varphi$ 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\pmod{t}\}$

• $\{a:a\equiv 1\pmod{m}\text{ and }a\equiv 1\pmod{n}\}$

Now the number of positive integers not greater than $t$ and coprime with $t$ is precisely $\varphi(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, $\varphi(mn)=\varphi(m)\varphi(n)$.

Title proof that Euler $\varphi$ function is multiplicative ProofThatEulervarphiFunctionIsMultiplicative 2013-03-22 15:03:40 2013-03-22 15:03:40 Wkbj79 (1863) Wkbj79 (1863) 12 Wkbj79 (1863) Proof msc 11A25 EulerPhiFunction MultiplicativeFunction EulerPhifunction