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.