📂Number Theory

Torsion Function

See Also

• Totient Function in Analytic Number Theory

Definition ¹

The function defined as follows, $\phi$, is called the Euler’s 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 term totient comes from the Tot- in Total meaning the whole and -tient from Quo-tient meaning the quotient. It can be understood in this way though it’s not used outside of mathematics, more specifically number theory, where it’s often referred to as the Phi function.

Start by manually calculating from $1$ to about $10$ to get the hang of 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, it may be wondered why such a seemingly difficult and irregular function is necessary. It turns out that it has many beautiful properties and serves as a foundation for various theories.

Theorem

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

Proof

Strategy: The function value for the power of a prime can easily be counted.

---

Since $p$ is a prime, for any $n \in \mathbb{N}$, $\gcd (p, np) \ne 1$ namely $$ 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\} $$ There are exactly $p^{k-1}$ such, therefore, $\phi (p^{k}) = p^{k} - p^{k-1}$

■