Suppose that $t=mn$ where $m,n$ are coprime. The Chinese remainder theorem 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\equiv1\pmod{m}{ and } a\equiv1\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)$ .