logo

Torsion Function 📂Number Theory

Torsion Function

See Also

Definition 1

The function defined as follows, ϕ\phi, is called the Euler’s totient function.

ϕ(m):={a  1amgcd(a,m)=1}=mpm(11p) \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 11 to about 1010 to get the hang of it. ϕ(1)={1}=1=1ϕ(2)={1}=212=1ϕ(3)={1,2}=323=2ϕ(4)={1,3}=412=2ϕ(5)={1,2,3,4}=545=4ϕ(6)={1,5}=61223=2ϕ(7)={1,2,3,4,5,6}=767=6ϕ(8)={1,3,5,7}=812=4ϕ(9)={1,2,4,5,7,8,}=923=6ϕ(10)={1,3,7,9}=101245=4 \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 pp, then ϕ(pk)=pkpk1\phi (p^{k}) = p^{k} - p^{k-1}

Proof

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


Since pp is a prime, for any nNn \in \mathbb{N}, gcd(p,np)1\gcd (p, np) \ne 1 namely p,2p,(pk12)p,(pk11)p,pk{a  1apkgcd(a,pk)=1} 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 pk1p^{k-1} such, therefore, ϕ(pk)=pkpk1\phi (p^{k}) = p^{k} - p^{k-1}


  1. Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p72. ↩︎