Properties of Euler's Totoent Function
Euler's totient function is defined as
ie the number of positive integers less than or equal to
relatively prime to
The function has the following properties:
a)
b)
(1) where
c)
if
d)
divides
implies
divides
e)
is even for
Also ifhas
distinct odd prime factors then
divides
Proof:
a)We can put
in the formula for:
b)Note that each prime divisor of mn is either a prime divisor of m or of n, and those primes which divide both m and n also divide gcd(m,n). Hence
From which we get (1) on multiplying by
c)Put
in (1)
d)We deduce d) from b). Sincedivides
we can write
where
If
then 
and d) is satisfied, so assume
and
then from b)
(2) where
Now use induction on
is trivial. Suppose d) holds for all
then it holds for
so
since
Then the right hand side of (2) is a multiple of
which means that
e)If
a) shows that
is even. If n contains at least one odd prime factor we write
where
The coefficient of
is even sois even. Each prime factor contributes a factor 2 to this coefficient so
if
has
distinct odd prime factors.
