Euler's Totient Function

Euler's totient function (also called the Phi function) counts the number of positive integers less than \(n\) that are coprime to \(n\). That is, \(\phi(n)\) is the number of \(m\in\mathbb{N}\) such that \(1\le m \lt n\) and \(\gcd(m,n)=1\).

The totient function appears in many applications of elementary number theory, including Euler's theorem, primitive roots of unity, cyclotomic polynomials, and constructible numbers in geometry.

The values of \(\phi(n)\) for \(n \le 100.\)

Find \(\phi(15).\)

---

Among positive numbers less than 15, eliminate multiples of 3 or 5, which are \(\{3, 5, 6, 9, 10, 12\}.\) The remaining numbers are \(\{1, 2, 4, 7, 8, 11, 13, 14\},\) so \(\phi(15)=8.\) \(_\square\)

The goal of this section will be to prove the formula for \( \phi(n)\): if \(p_1,p_2,\ldots,p_k\) are the distinct primes dividing \(n,\) then

\[\phi(n) = n \left( 1 - \frac1{p_1} \right) \left( 1-\frac1{p_2} \right) \cdots\left( 1-\frac1{p_k} \right).\]

The proof begins with some preliminaries about the properties of \(\phi.\) In particular, the set in the definition of \(\phi,\) consisting of positive integers \( \le n\) which are relatively prime to \(n,\) has a name; it is denoted

\[({\mathbb Z}/n)^* = \{m \in {\mathbb N} \colon 1 \le m \le n, \gcd(m,n)=1\}.\]

So \(\phi(n)\) equals the size of \( ({\mathbb Z}/n)^*.\)

Omitting the requirement about the GCD gives the full set \( {\mathbb Z}/n, \) which has \(n\) elements and can be thought of as the integers modulo \(n.\) The subset \( ({\mathbb Z}/n)^*\) is precisely the set of units in \( {\mathbb Z}/n\). Units are the elements with multiplicative inverses. This is equivalent to being coprime to \(n,\) by Bezout's identity.

The totient function is multiplicative: \(\phi(ab)=\phi(a)\phi(b)\) if \(\text{gcd}(a,b)=1.\)

The left side counts elements \(z \in ({\mathbb Z}/ab)^* \) and the right side counts ordered pairs \((x,y),\) where \(x \in ({\mathbb Z}/a)^*\) and \(y \in ({\mathbb Z}/b)^*\). The identity will be proved by exhibiting a bijection \(f\) between the two sets.

This is essentially the Chinese remainder theorem: let \(f(z)\) be the ordered pair \( (z \text{ mod } a, z \text{ mod }b).\) This is a bijection whose inverse is the map that sends an ordered pair \((x,y)\) to the unique solution mod \(ab\) to the congruences

\[\begin{align} z &\equiv x \pmod a \\ z &\equiv y \pmod b. \end{align}\]

Note that \(z\) is relatively prime to \(ab\) if and only if it is relatively prime to \(a\) and to \(b.\) So \(f\) is indeed a bijection between \(({\mathbb Z}/ab)^*\) and \(({\mathbb Z}/a)^* \times ({\mathbb Z}/b)^*,\) as desired. \(_\square\)

As with any multiplicative function, computing \(\phi(n)\) can be reduced to factoring \(n\) as a product of prime powers, \(n=p_1^{e_1}\ldots p_k^{e_k},\) and expressing \(\phi(n)\) as the product of the \(\phi\left(p_i^{e_i}\right).\)

Consider \(\phi\left(p^{e}\right)\) where \(p\) is a prime. Then the positive integers in the range \(\left[1,p^{e}\right]\) that are not coprime to \(p^{e}\) are the multiples of \(p\) in that range. There are \(p^{e-1}\) of these, so

\[\phi\left(p^e\right)=p^e-p^{e-1}=p^e\left(1-\frac1p\right).\]

This leads to a formula for \(\phi(n)\):

If \(n=p_1^{e_1}\ldots p_k^{e_k},\) where \(p_i\) are primes and \( e_i > 0,\) then

\[ \phi(n) = n\left( 1-\frac1{p_1}\right) \left( 1-\frac1{p_2} \right) \cdots\left( 1-\frac1{p_k} \right). \]

By multiplicativity,

\[ \begin{align} \phi(n)=\phi\big(p_1^{e_1}\ldots p_k^{e_k}\big)&=\phi\big(p_1^{e_1}\big)\ldots\phi\big(p_k^{e_k}\big) \\ &=p_1^{e_1}\left( 1-\frac1{p_1}\right) \cdots p_k^{e_k} \left( 1-\frac1{p_k} \right) \\ &= \big(p_1^{e_1}\ldots p_k^{e_k}\big) \left( 1-\frac1{p_1} \right) \cdots \left( 1-\frac1{p_k} \right) \\ &= n\left( 1-\frac1{p_1} \right) \cdots \left( 1-\frac1{p_k} \right).\ _\square \end{align} \]

This formula can also be proved directly by a sieving argument; as in the example in the introduction, remove multiples of the \( p_i,\) but since numbers can be multiples of more than one of the primes, counting them correctly requires the principle of inclusion-exclusion.

How many positive integers less than \( 900\) are relatively prime to \(900?\)

---

Compute

\[ \phi(900) = 900\left( 1-\frac12 \right) \left( 1-\frac13 \right) \left( 1-\frac15 \right) = 240.\ _\square \]

Multiplicativity: The formula for \(\phi(n)\) can be used to prove the following result, which generalizes the multiplicativity of \(\phi\):

Let \(d=\gcd(a,b).\) Then \( \phi(ab) = \phi(a)\phi(b) \frac{d}{\phi(d)}.\)

Factoring and RSA: Note that the formula for \(\phi\) involves knowing the prime factorization of \(n.\) For numbers \(n\) which are the products of two distinct primes, a sort of converse is true. That is, given \(n\) and \(\phi(n),\) and the information that \(n=pq\) for distinct primes \(p\) and \(q,\) it is straightforward to recover \(p\) and \(q.\)

To see this, note that \( \phi(n) = (p-1)(q-1),\) so \(n-\phi(n)+1 = p+q.\) Knowing \(p+q\) and \(pq\) is enough to find \(p\) and \(q\): the polynomial \( x^2 - \big(n-\phi(n)+1\big) x + n\) factors as \( (x-p)(x-q),\) so the two roots \(p,q\) are easy to recover via the quadratic formula.

This is important in the discussion of the security of RSA encryption; the strength of the encryption method rests on the secrecy of \(\phi(n),\) and the above paragraph shows that this is equivalent to factoring \(n,\) which is widely believed to be a very hard problem in general.

Divisor sum: This is one of the most well-known properties of \(\phi(n),\) and it is discussed in the wiki on multiplicative functions: \[ \sum_{d|n} \phi(d) = n. \] There are several ways to prove this, but an appealingly direct way proceeds as follows:

Consider the fractions \( \frac1{n}, \frac2{n}, \ldots, \frac{n}{n}.\) There are obviously \(n\) of these. Reduce them all to lowest terms. The new fractions on the list will all be of the form \( \frac{a}{d},\) where \(d|n\) and \(a\) is relatively prime to \(d.\) And it's straightforward to see that all fractions of this type will show up somewhere on the list.

The number of such fractions with denominator \(d\) is \( \phi(d),\) so the total number is \( \sum\limits_{d|n} \phi(d).\) This shows that \( \sum\limits_{d|n}\phi(d) = n,\) as desired.

How many numbers in \(\{1, 2, \dots, 200\}\) are coprime to 100?

---

There are \(\phi(100) = (4-2)(25-5) = 40\) coprime numbers to 100 in \(\{1, 2, \dots, 100\}.\)

Since \(\gcd(a,b) = \gcd(a-b,b),\)

\[\begin{align} \gcd(101, 100) =& \gcd(1, 100), \\ \gcd(102, 100) =& \gcd(2, 100), \\ \vdots& \\ \gcd(200, 100) =& \gcd(100, 100). \end{align}\]

So there are \(\phi(100) = 40\) coprime numbers to 100 in \(\{101, 102, \dots, 200\}.\) So the answer is \(40+40= 80.\) \(_\square\)

Find the number of positive integers \(n\le 168\) such that \(\gcd(n,168)=8.\)

---

These are the positive integers of the form \(8m,\) where \(m \le 21\) and \(\gcd(m,21)=1.\) So the answer is \(\phi(21) = (3-1)(7-1) = 12. \) \(_\square\)

Let \(n\) be a positive integer, then find

(a) the sum of all the positive integers less than \(n\) and relatively prime to \(n\);
(b) the sum of all the positive integers less than \(2n\) and relatively prime to \(n\).

---

(a) Let \(S\) be the value of \(\displaystyle \sum_{d<n,\gcd(d,n)=1} d\) and \(d_1<d_2<d_3<\ldots < d_{\phi(n)}\) be the positive numbers less than \(n\) and relatively prime to \(n\). Also note that \(\gcd(d,n)=1\) only if \(\gcd(n-d,n)=1\). Then \[d_1+d_{\phi(n)}=n,\ d_2+d_{\phi(n)-1}=n ,\ \text{ and so on}\implies S=\dfrac{n\phi(n)}{2}.\]

(b) We have to find

\[\begin{align} \sum_{d<n , \gcd(d,n)=1} d +\displaystyle \sum_{n<d<2n , \gcd(d,n)=1} d &=S+\displaystyle \sum_{n<d<2n , \gcd(d,n)=1} d \\ &= S+\displaystyle \sum_{d<n , \gcd(d,n)=1} (n+d) \\ &=S+n\phi(n)+\displaystyle \sum_{d<n, \gcd(d,n)=1} d \\ &= 2S+n\phi(n)\\ &=2n\phi(n).\ _\square \end{align}\]