📂Number Theory

Totient Function

See Also

• The Totient Function in Analytic Number Theory

Definition ¹

The $\phi$ defined as follows is called the Euler totient function.

$$ \phi ( m ) := \left| \left\{ a \ | \ 1 \le a \le m \land \gcd (a,m) = 1 \right\} \right| = m \prod_{p \mid m} \left( 1 - {{1} \over {p}} \right) $$

Explanation

The word totient can reasonably be understood as arising from combining the Tot- of Tot-al, meaning the whole, with the -tient of Quo-tient, meaning quotient. It is used almost nowhere outside mathematics—and even within mathematics only in number theory—and even there it is frequently written as the Phi function or the Phi function.

Let us compute directly from $1$ up to about $10$ to get a feel for it. $$ \begin{align*} \phi ( 1 ) = & \left| \left\{ 1 \right\} \right| = 1 =1 \\ \phi ( 2 ) = & \left| \left\{ 1 \right\} \right| = 2 {{1} \over {2}} = 1 \\ \phi ( 3 ) = & \left| \left\{ 1 , 2 \right\} \right| = 3 {{2} \over {3}} = 2 \\ \phi ( 4 ) = & \left| \left\{ 1 , 3 \right\} \right| = 4 {{1} \over {2}} = 2 \\ \phi ( 5 ) = & \left| \left\{ 1 , 2 , 3 , 4 \right\} \right| = 5 {{4} \over {5}} = 4 \\ \phi ( 6 ) = & \left| \left\{ 1 , 5 \right\} \right| = 6 {{1} \over {2}} {{2} \over {3}} = 2 \\ \phi ( 7 ) = & \left| \left\{ 1 , 2 , 3 , 4 , 5 , 6 \right\} \right| = 7 {{6} \over {7}} = 6 \\ \phi ( 8 ) = & \left| \left\{ 1 , 3 , 5 , 7 \right\} \right| = 8 {{1} \over {2}} = 4 \\ \phi ( 9 ) = & \left| \left\{ 1 , 2, 4 , 5 , 7, 8, \right\} \right| = 9 {{2} \over {3}} = 6 \\ \phi ( 10 ) = & \left| \left\{ 1 , 3 , 7 , 9 \right\} \right| = 10 {{1} \over {2}} {{4} \over {5}} = 4 \end{align*} $$

At first glance one might wonder why such a function—so hard to compute and seemingly without any rule—is even needed. As it turns out, it not only possesses an abundance of beautiful properties but also serves as the foundation supporting various theories.

Theorem

For a prime $p$, $\phi (p^{k}) = p^{k} - p^{k-1}$

Proof

Strategy: The function value for a power of a prime can be easily obtained through counting.

---

Since $p$ is prime, for any $n \in \mathbb{N}$ we have $\gcd (p, np) \ne 1$, that is $$ p , 2p , \cdots (p^{k-1} - 2 ) p , (p^{k-1} - 1 ) p , p^{k} \notin \left\{ a \ | \ 1 \le a \le p^{k} \land \gcd (a,p^{k}) = 1 \right\} $$ Since there are exactly $p^{k-1}$ of these, $\phi (p^{k}) = p^{k} - p^{k-1}$

■