Euler's totient function

Euler's totient function, $\displaystyle \phi(n)$ , is defined as the number of positive integers less than or equal to a given positive integer that is relatively prime to that integer. $\displaystyle \phi(n)$ is read "phi of n."

Formulas

To derive the formula, let us first define the prime factorization of $n$ as $n = p_1^{e_1}p_2^{e_2}\cdot p_n^{e_n}$ where the $\displaystyle p_i$ are primes. Now, we can use a PIE argument to count the number of numbers less than or equal to $n$ that are relatively prime to it.

First, let's count the complement of what we want (i.e. all the numbers less than $n$ that share a common factor with it). There are $p_1^{e_1-1}p_2^{e_2}\cdots p_n^{e_n}$ numbers less than $n$ that are divisible by $p_1$ . If we do the same for each $p_k$ and add these up, we get

$p_1{e_1-1}p_2^{e_2}\cdots p_n{e_n} + p_1^{e_1}p_2^{e_2-1}\cdots p_n^{e_n} + \cdots + p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n - 1}.$

We can factor out, though:

$p_1^{e_1-1}p_2^{e_2-1}\cdots p_n^{e_n-1}(p_1+p_2+\cdots + p_n).$

But we are obviously overcounting. We then subtract out those divisible by two of the $p_1$ . We continue with this PIE argument to figure out that the number of elements in the complement of what we want is

$p_1^{e_1-1}p_2^{e_2-1}\cdots p_n^{e_n-1}[(p_1+p_2+\cdots+p_n)-(p_1p_2+p_1p_3+\cdots+(-1)^np_{n-1}p_n)+\cdots+p_1p_2\cdots p_n]$

which we can factor further as

$p_1^{e_1-1}p_2^{e_2-1}\cdots p_n^{e_n-1}(p_1-1)(p_2-1)\cdots(p_n-1).$

Making one small adjustment, we write this as

$\phi(n) = n\left(1-\frac 1{p_1}\right)\left(1-\frac 1{p_2}\right)\cdots\left(1-\frac 1{p_n}\right).$

Given the general prime factorization of ${n} = {p}_1^{e_1}{p}_2^{e_2} \cdots {p}_m^{e_m}$ , one can compute $\phi(n)$ using the formula $\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots \left(1-\frac{1}{p_m}\right)$ .