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(*p*^{n}). Think about the
*p*^{n} numbers *1,2,....,p*^{n}.
Which of these numbers is divisible by *p*? Clearly
the answer is *p,2p,3p,...,p*^{n}. Thus in
our original list every *p*
numbers we get a number divisible by *p*.
There are *p*^{n}/p=p^{n-1}
such numbers and so counting the numbers from *1,...,p*^{n}
coprime to *p* we get:

phi(*p*^{n})=*p*^{n}-p^{n-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

**Z**_{mn}
is isomorphic to the

direct product
**Z**_{m}x**Z**_{n}.

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(**Z**_{mn}) = U(**Z**_{m})xU(**Z**_{n}).

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.