determinationofeuler'sphifunctionforanyi

Determination of Euler's Phi Function for any Integer

If n=(p1**k1)(p2**k2)(p3**k3)…(pr**kr)

phi(n)=n(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pr)

Proof:

(By induction from the following lemmas)

LEMMA 1

phi(p**k) = p**k - p**(k-1)

Proof:

There are p**(k-1) integers between 1 and p**k which are divisible by p, and these are the only ones which share a common factor with p**k

LEMMA 2

phi(mn) = phi(m)phi(n) [hcf (m,n)=1]

Proof:

Arrange the integers from 1 to mn in m columns of n integers (rows). phi(mn) equals the number of these relatively prime to both m and n.

hcf (qm+r, m) = hcf (r,m), so rth column relatively prime to m iff r relatively prime to m.

Entries in the rth column are: r, m+r, 2m+r, …, (n-1)m+r

hcf (m,n)=1 => km<>jm [mod n][k<>j] => km+r<>jm+r [mod n][k<>j]

Therefore the rth column contains the numbers congruent [mod n] to 0, 1, 2, …, (n-1) in some order

i.e. a total of phi(n) numbers relatively prime to n, in that column.

But there are a total of phi(m) such columns, and hence result follows