4.4: Euler’s Phi or Totient Function
- Page ID
- 60317
Recall the phi function from Definition 4.9.
Lemma 4.15 (Gauss)
For \(n \in \mathbb{N} : n = \sum_{d|n} \varphi (d)\).
- Proof
-
Define \(S(d,n)\) as the set of integers \(m\) between \(1\) and \(n\) such that \(\gcd (m, n) = d\):
\[S(d, n) = \{m \in \mathbb{N} | m \le n \mbox{ and } \gcd (m,n) = d\} \nonumber\]
This is equivalent to
\[S(d, n) = \{m \in \mathbb{N} | m \le n \mbox{ and } \gcd (md, dn) = 1\} \nonumber\]
From the definition of Euler’s phi function, we see that the cardinality \(|S(d,n)|\) of \(S(d, n)\) is given by \(\varphi(\frac{n}{d})\). Thus we obtain:
\[n = \sum_{d|n} |S(d,n)| = \sum_{d|n} \varphi(\frac{d}{n}) \nonumber\]
As \(d\) runs through all divisors of \(n\) in the last sum, so does \(\frac{n}{d}\). Therefore the last sum is equal to \(\sum_{d|n} \varphi(d)\), which proves the lemma.
Theorem 4.16
Let \(\prod_{i=1}^{r} p_{i}^{l_{i}}\) be the prime power factorization of \(n\). Then
\[\varphi (n) = \prod_{i=1}^{r} (1-\frac{1}{p_{i}}) \nonumber\]
- Proof
-
Apply Mobius inversion to Lemma 4.15:
\[\varphi (n) = \sum_{d|n} \mu (d) \frac{n}{d} = n \sum_{d|n} \frac{\mu (d)}{d} \nonumber\]
The functions \(\mu\) and \(d \rightarrow \frac{1}{d}\) are multiplicative. It is easy to see that the product of two multiplicative functions is also multiplicative. Therefore \(\varphi\) is also multiplicative (Proposition 4.3). Thus
\[\varphi (\prod_{i=1}^{r} p_{i}^{l_{i}} = \prod_{i=1}^{r} \varphi (p_{i}^{l_{i}}) \nonumber\]
So it is sufficient to evaluate the function \(\varphi\) on prime powers. Noting that the divisors of the prime power \(p^l\) are \(\{1, p, \cdots p^l\}\), we get from Equation
\[\varphi (p^l) = p^{l} \sum_{j=0}^{l} \frac{\mu (p^j)}{p^j} = p^{l} (1-\frac{1}{p}) \nonumber\]
Substituting this into Equation 4.4 completes the proof.
From this proof we obtain the following corollary.
Corollary 4.17
Euler’s phi function is multiplicative.