Skip to main content
Mathematics LibreTexts

4.4: Euler’s Phi or Totient Function

  • Page ID
    60317
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    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.


    This page titled 4.4: Euler’s Phi or Totient Function is shared under a CC BY-NC license and was authored, remixed, and/or curated by J. J. P. Veerman (PDXOpen: Open Educational Resources) .

    • Was this article helpful?