First read Euler Phi function
to see its definition,
the statement of its properties, and the notation.
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:
The multiplicative property of the phi function will be proved
using a little ring theory
are coprime an appeal to
the Chinese remainder theorem
shows us that
is isomorphic to the direct product
Now for any ring R
let's write U(R)
s of R
. It is very easy to
see that for a direct product of rings RxS
In detail, (a,b)
is a unit iff there exists
. That is true iff
. That is, a
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
So we deduce that phi(mn
), as required.