Euler's $\phi$ function is multiplicative
We define $U_k = \{x\in Z_k \;| \;(x,k)=1\}$ So clearly $\phi(k)=|U_k|$
Let $(m,n)=1$
Want to show : $\phi(mn)=\phi(m)\cdot \phi(n)$ or $|U_{mn}|=|U_m|\cdot |U_n|$
I want to produce a bijection from $U_{mn} \to U_m \times U_n$
I define $$f:U_{mn} \to U_m \times U_n$$
$$f(a \pmod{mn}) = (a \pmod{m}, \;a\pmod{n}) \;\; \forall a\in U_{mn}$$
Note that for $a,b\in U_{mn}$, we have $a=b \iff a \pmod {mn} = b\pmod{mn}$
so let $a,b\in U_{mn}$ such that $a \pmod{mn} =b \pmod{mn} \rightarrow a=b $, then,
$f(a \pmod{mn}) = (a \pmod{m}, \;a\pmod{n}) = (b \pmod{m}, \;b\pmod{n}) = f(b \pmod{mn})$. So it is well defined.
Also, if $f(a \pmod{mn}) =f(b \pmod{mn})$ for some $a,b \in U_{mn}$
$\rightarrow (a \pmod{m}, \;a\pmod{n}) = (b \pmod{m}, \;b\pmod{n})$
$\rightarrow a \pmod{m}= b \pmod{m}$ and $a\pmod{n} =b\pmod{n}$
$\rightarrow a\equiv b\pmod m$ and $a\equiv b\pmod n$
Because $(m,n)=1$
$\rightarrow a\equiv b \pmod{mn}$
$\rightarrow a \pmod {mn} = b\pmod{mn}$
$\rightarrow a=b$ because $a,b \in U_{mn}$
So it is injective.
Now let $(a,b) \in U_m \times U_n$
$\rightarrow a\in U_m$ and $b\in U_n$
$\rightarrow (a,m)=1$ and $(b,n)=1$
$now \exists ab \pmod{mn} \in U_{mn}$
such that $f((ab \pmod{mn}) \pmod{mn}) = f(ab \pmod{mn}) = (ab \pmod m, ab\pmod n) = ?$ (Getting stuck here, help please)
Hint: By Bezout's identity there are $x, y\in\Bbb Z$ such that $xm+yn=1$.
Use $x, y$ to express a number $s$ that satisfies $s\equiv a\pmod m$ and $s\equiv b\pmod m$.