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{aligned} z &\equiv x \pmod a \\ z &\equiv y \pmod b. \end{aligned}$$

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{aligned} \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{aligned}$$

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{aligned} \gcd(101, 100) =& \gcd(1, 100), \\ \gcd(102, 100) =& \gcd(2, 100), \\ \vdots& \\ \gcd(200, 100) =& \gcd(100, 100). \end{aligned}$$

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{aligned} \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{aligned}$$