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