Definition of Euler’s totient function $\varphi$

Euler’s totient function $\varphi$ counts the number of positive integers less than or equal to $n$ that are relatively prime (coprime) to $n$:

\[\begin{aligned} \forall n \in \mathbb{N}^*, \varphi(n) &=\operatorname{card}\{1\leqslant k\leqslant n \mid \operatorname{gcd}(k,n)=1\} \\ &=\sum_{k=1}^{n} [\gcd(k,n) = 1] \end{aligned}\]

where $\gcd(a,b)$ is the greatest common divisor of $a$ and $b$, and $[P]$ is the Iverson bracket, which is defined as:

\[[P] = \begin{cases} 1 & \text{if $P$ is true} \\ 0 & \text{if $P$ is false} \end{cases}\]

Euler’s totient function has a number of interesting properties, including the following

Some properties of Euler’s totient function $\varphi$

Euler’s totient function $\varphi$ counts the number of positive integers less than or equal to $n$ that are relatively prime (coprime) to $n$:

\[\forall n \in \mathbb{N}^*, \varphi(n)=\operatorname{card}\{1\leqslant k\leqslant n \mid \operatorname{gcd}(k,n)=1\}\]

For example, $\varphi(9) = 6$ because ${1, 2, 4, 5, 7, 8}$ are all relatively prime to $9$.

Exercise 1. Show that if $n$ is prime, then $\varphi(n) = n-1$

Exercise 2. Invertible elements in $\mathbb{Z} / n \mathbb{Z}$ for a group under multiplication, denoted by \((\mathbb{Z} / n \mathbb{Z})^{\times}=\{x \in \mathbb{Z} / n \mathbb{Z} \mid x \text { invertible }\} \text {. }\)

Show that: $\forall n \geq 2, \varphi(n)=\operatorname{card}{\left(\mathbb{Z} / n \mathbb{Z}^{\times})\right.}$

Exercise 3. Using the Chinese Remainder Theorem, if $m$ and $n$ are relatively prime, there exists a ring isomorphism:

\[\mathbb{Z} / n m \mathbb{Z} \simeq \mathbb{Z} / n \mathbb{Z} \times \mathbb{Z} / m \mathbb{Z}\]

Show that for $m$ and $n$ relatively prime, we have: $\varphi(mn) = \varphi(m)\varphi(n)$

In other words, $x, y \in(\mathbb{Z} / n \mathbb{Z})^{\times} \Longrightarrow x y \in(\mathbb{Z} / n \mathbb{Z})^{\times}$. Definition Euler’s totient function is \(\phi(n)=\#(\mathbb{Z} / n \mathbb{Z})^{\times}=\#\{0 \leqslant x<n \mid \operatorname{gcd}(x, n)=1\}\)

Solutions

Exercise 1. Show that if $n$ is prime, then $\varphi(n) = n-1$

Solution. Euler’s totient function $\varphi$ counts the number of positive integers less than or equal to $n$ that are relatively prime (coprime) to $n$.

\[\begin{aligned} \forall n \in \mathbb{N}^*, \varphi(n) &=\operatorname{card}\{1\leqslant k\leqslant n \mid \operatorname{gcd}(k,n)=1\} \\ &=\sum_{k=1}^{n} [\gcd(k,n) = 1] \end{aligned}\]

where $\gcd(a,b)$ is the greatest common divisor of $a$ and $b$, and $[P]$ is the Iverson bracket, which is defined as:

\[[P] = \begin{cases} 1 & \text{if $P$ is true} \\ 0 & \text{if $P$ is false} \end{cases}\]

Consider the definition of a prime number, the only positive integer less than or equal to a prime $n$ which is not prime to $n$ is $n$ itself. If $n$ is a prime

\[\underbrace{\operatorname{gcd}(k,n)=1, \quad \forall k \in \llbracket1,n \llbracket}_{n-1 \text{ numbers}}\text{ and } \operatorname{gcd}(n,n)=n\] \[\color{green}{\varphi(n)=\operatorname{card}\{1\leqslant k\leqslant n \mid \operatorname{gcd}(k,n)=1\}=n-1}\]

Exercise 2. Invertible elements in $\mathbb{Z} / n \mathbb{Z}$ for a group under multiplication, denoted by \((\mathbb{Z} / n \mathbb{Z})^{\times}=\{\bar{x} \in \mathbb{Z} / n \mathbb{Z} \mid \bar{x} \text { invertible }\} \text {. }\)

Show that: $\forall n \geq 2, \varphi(n)=\operatorname{card}{(\mathbb{Z} / n \mathbb{Z})^{\times}}$

Solution. Let $\bar{x}\in(\mathbb{Z} / n \mathbb{Z})^{\times}, \bar{x} \text { invertible }$:

\[\begin{aligned} & \Longleftrightarrow \exists\bar{y}\in(\mathbb{Z} / n \mathbb{Z})^{\times} \mid \bar{x} \cdot\bar{y}=\overline{1} \\ & \Longleftrightarrow \exists\bar{y}\in(\mathbb{Z} / n \mathbb{Z})^{\times} \mid\overline{xy} =\overline{1} \text { since } (\mathbb{Z} / n \mathbb{Z})^{\times}\text { is a group for muliplication }\\ & \Longleftrightarrow \exists x, y \in \mathbb{Z} \mid x y \equiv 1 \bmod n \\ & \Longleftrightarrow \exists x, y \in \mathbb{Z} \mid x y=1+n k \text { for some } k \in \mathbb{Z} \\ & \Longleftrightarrow \exists x, y \in \mathbb{Z} \mid x y-n k=1 \text { for some } k \in \mathbb{Z} \\ & \Longleftrightarrow\operatorname{gcd}(x, n)=1 \text{ using Bézout's Identity} \end{aligned}\]

Bézout’s identity — For nonzero integers $a$ and $b$, let $d$ be the greatest common divisor $d=\operatorname{gcd⁡}(a,b)$. Then, there exist integers $u$ and $v$ such that $au+bv=d$

Here: $d=1=\operatorname{gcd}⁡(a=x,b=n)$, $⁡u=y$ and $v=-k$.

Euler’s totient function $\varphi$ counts the number of positive integers less than or equal to $n$ that are relatively prime (coprime) to $n$:

\[\begin{aligned} \forall n \in \mathbb{N}^*, \varphi(n) &=\operatorname{card}\{1\leqslant x\leqslant n \mid \operatorname{gcd}(x,n)=1\} \end{aligned}\]

Conclusion. \(\color{green}{\operatorname{card}\left(\mathbb{Z} / n \mathbb{Z})^{\times}\right.=\operatorname{card}\{\bar{x} \in \mathbb{Z} / n \mathbb{Z} \mid \bar{x} \text { invertible }\}=\operatorname{card}\{1\leqslant x\leqslant n \mid \operatorname{gcd}(x,n)=1\}=\varphi(n)}\)

Exercise 3. Using the Chinese Remainder Theorem, if $m$ and $n$ are relatively prime, there exists a ring isomorphism:

\[\mathbb{Z} / mn \mathbb{Z} \simeq \mathbb{Z} / m \mathbb{Z} \times \mathbb{Z} / n \mathbb{Z}\]

Show that for $m$ and $n$ relatively prime, we have: $\varphi(mn) = \varphi(m)\varphi(n)$, where the Euler’s totient function $\varphi$ counts the number of positive integers less than or equal to $n$ that are relatively prime (coprime) to $n$:

\[\begin{aligned} \forall n \in \mathbb{N}^*, \varphi(n) &=\operatorname{card}\{1\leqslant x\leqslant n \mid \operatorname{gcd}(x,n)=1\} \end{aligned}\]

Solution. We have seen in Exercise 2 that:

\[\forall n \geq 2, \varphi(n)=\operatorname{card}\{(\mathbb{Z} / n \mathbb{Z})^{\times}\}\] \[\begin{aligned} \text { Let }\mathbb{A} \text { and } \mathbb{B} \text { be two rings. } & (a, b) \text { is an invertible element of } \mathbb{A} \times \mathbb{B} \\ & \Leftrightarrow \exists\left(a^{\prime}, b^{\prime}\right) \in \mathbb{A} \times \mathbb{B},(a, b) \times\left(a^{\prime}, b^{\prime}\right)=\left(1_{\mathbb{A}}, 1_{\mathbb{B}}\right) \\ & \Leftrightarrow \exists a^{\prime} \in \mathbb{A}, \exists b^{\prime} \in \mathbb{B}, a \times a^{\prime}=1_{\mathbb{A}} \text { and } b \times b^{\prime}=1_{\mathbb{B}}\\ & \Leftrightarrow a \text { is an invertible element of } \mathbb{A} \text { and } b \text { is an invertible element of } \mathbb{B}\\ & \Leftrightarrow (\mathbb{A} \times \mathbb{B})^{\times}=\mathbb{A}^{\times} \times \mathbb{B}^{\times} \end{aligned}\]

Then we have: $(\mathbb{Z} / mn \mathbb{Z})^{\times} \simeq (\mathbb{Z} / m \mathbb{Z} \times \mathbb{Z} / n \mathbb{Z})^{\times}\simeq (\mathbb{Z} / m \mathbb{Z})^{\times} \times (\mathbb{Z} / n \mathbb{Z})^{\times} $

Conclusion.

\[\color{green}{\varphi(mn)=\operatorname{card}(\mathbb{Z} / mn \mathbb{Z})^{\times}=\operatorname{card}(\mathbb{Z} / m \mathbb{Z})^{\times} \times \operatorname{card}(\mathbb{Z} / n \mathbb{Z})^{\times}=\varphi(m)\times \varphi(n)}\]