proof of the properties of the Euler Phi function

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

phi(pⁿ)=pⁿ-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_mxZ_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.