Euler's Totient Function

Euler's Totient Function denoted by lower case Phi . Euler's Totient Function (m) returns the number of Integers less than m, including 1 that are relatively prime to m.

For m = p a prime:

(p) = p - 1

All numbers less than p are relatively prime and there are p - 1 of them.

(p) = p - 1
(7) = 7 - 1 = 6		1, 2, 3, 4, 5, 6

When m = p^a power of a prime.
The numbers that have a common factor with m are:
p, 2p, 3p, . . . ,p^(a-1)p
since there are p^(a-1) of them:
(p^a) = p^a - p^(a-1) = (p^(a-1))(p - 1) = (p^a)(1 - 1/p)

(25) = 52 - 5 = 5(5 - 1) = (52)(1 - 1/5) = 20

1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24

General Case: (m)

Let p be a prime dividing m, then the integers divisible by p are:
p, 2p, 3p, 4p, . . . , (m/p)(p)

There are m/p of them. The number of integers not divisible by p are:
m - m/p = m(1 - 1/p)

Let q be another prime dividing m. To find the number of integers divisible by neither p or q, we must deduct the m/q multiples of q:
q, 2q, 3q, . . . , (m/q)(q)

However, since some elements of p and q are common the m/pq multiples of pq are:
pq, 2pq, 3pq, . . . , (m/pq)(pq)

Therefore:

m/q - m/pq = (m/q)(1- 1/p)

Then the total of integrs not divisible by p or q is:
m(1 - 1/p) - (m/q)(1 - 1/p) = m(1 - 1/p)(1 - 1/q)

The General formula for Euler's Totient Function is:

(m) = m(1 - 1/p₁)(1 - 1/p₂)(1 - 1/p₃)( . . . )(1 - 1/p_n)

Where p₁, p₂, p₃, . . . , p_n are prime factors of m.

Example:

(60)	= 60(1 - 1/2)(1 - 1/3)(1 - 1/5)
	= (60 - 30)(1 - 1/3)(1 - 1/5)
	= (30)(1 - 1/3)(1 - 1/5)
	= (30 - 10)(1 - 1/5)
	= (20)(1 - 1/5)
	= (20 - 4)
	= 16	1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59