Euler Phi Function of an Integer

Theorem

Let $n \in \Z_{>0}$, that is, a positive integer.

Let $\phi: \Z_{>0} \to \Z_{>0}$ be the Euler $\phi$-function.

Then for any $n \in \Z_{>0}$, we have:

$\displaystyle \phi \left({n}\right) = n \left({1 - \frac 1 {p_1}}\right) \left({1 - \frac 1 {p_2}}\right) \ldots \left({1 - \frac 1 {p_r}}\right)$

where $p_1, p_2, \ldots, p_r$ are the distinct primes dividing $n$.

Or, more compactly:

$\displaystyle \phi \left({n}\right) = n \prod_{p \backslash n} \left({1 - \frac 1 {p}}\right)$

Corollary

If $p$ divides $n$, where $p$ is prime, then $p - 1$ divides $\phi \left({n}\right)$.

Proof

We express $n$ in its Prime Decomposition:

$n = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}, p_1 < p_2 < \ldots < p_r$

as we determined it was always possible to do.

As all primes are, by definition, coprime, then from Euler Phi Function is Multiplicative we have:

$\phi \left({n}\right) = \left({p_1^{k_1}}\right) \left({p_2^{k_2}}\right) \cdots \left({p_r^{k_r}}\right)$

and from Euler Phi Function of a Prime, we have:

$\displaystyle \phi \left({p^{k}}\right) = p^{k} \left({1 - \frac 1 {p}}\right)$

So:

$\displaystyle \phi \left({n}\right) = p_1^{k_1} \left({1 - \frac 1 {p_1}}\right) p_2^{k_2} \left({1 - \frac 1 {p_2}}\right) \cdots p_r^{k_r} \left({1 - \frac 1 {p_r}}\right)$

and the result follows directly from $n = p_1^{k_1} p_2^{k_2} \ldots p_r^{k_r}$.

$\blacksquare$

Alternative Formulation

It can be seen from the derivation of the proof that there is an alternative formulation for $\phi \left({n}\right)$:

$\displaystyle \phi \left({n}\right) = p_1^{k_1-1} p_2^{k_2-1} \cdots p_r^{k_r-1} \left({p_1 - 1}\right) \left({p_2 - 1}\right) \cdots \left({p_r - 1}\right) = \prod_{1 \le i \le r} p_i^{k_i - 1} \left({p_i - 1}\right)$

in which some (or possibly all) of the exponents $k_j - 1$ may be zero.

Proof of Corollary

Follows directly from the alternative formulation above.

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 25$