| First read Euler Phi function to see its definition,
the statement of its properties, and the notation.
Proof:
That phi(p)=p-1 for a prime p is clear,
since all of the numbers 1,...,p except the last one
are coprime to p.
Let us compute phi(pn). Think about the
pn numbers 1,2,....,pn.
Which of these numbers is divisible by p? Clearly
the answer is p,2p,3p,...,pn. Thus in
our original list every p
numbers we get a number divisible by p.
There are pn/p=pn-1
such numbers and so counting the numbers from 1,...,pn
coprime to p we get:
phi(pn)=pn-pn-1
The multiplicative property of the phi function will be proved
using a little ring theory.
Since m and n are coprime an appeal to
the Chinese remainder theorem shows us that
Zmn
is isomorphic to the direct product
ZmxZn.
Now for any ring R let's write U(R) for the
multiplicative group of units of R. It is very easy to
see that for a direct product of rings RxS we have
that U(RxS)=U(R)xU(S).
In detail, (a,b) in RxS is a unit iff there exists
(c,d) with (a,b)(c,d)=(1,1)=(c,d)(a,b). That is true iff
ac=1=ca and bd=1=db. That is, a and b
are units. Hence the claim.
So in our case we see that
U(Zmn) = U(Zm)xU(Zn).
Therefore both of these sets have the same number of elements.
As is explained in the integers modulo n writeup the number of
units of the ring of integers mod n is phi(n).
So we deduce that phi(mn)=phi(m)phi(n), as required. | 
