Totient Function

Math NT

Definition

Euler’s totient function returns the number of integers from $1\le k\le n$ for a positive integer $n$. It is notated as:

$$\varphi (n)$$

$\varphi (n)$ for Prime Powers

Through prime factorization, for $p^k$, the only positive integers below $p^k$ where $\gcd (p^k,n)>1$ is where $n=mp$, for $1\le m\le p^{k-1}$. Therefore:

$$\begin{gathered} \varphi (p^k) \\ =p^k-p^{k-1} \\ =p^{k-1}(p-1) \\ {p}^k(1-\frac{1}{p}) \end{gathered}$$

Multiplicative Property of $\varphi$

If $m$ and $n$ are coprime:

$$\varphi (m)\varphi (n)=\varphi (mn)$$

Proof: Let set $A$ be all numbers coprime to $m$ below $m$, and set $B$ be all numbers coprime to $n$ below $n$.

$$\begin{gathered} |A|=\varphi (m) \\ |B|=\varphi (n) \end{gathered}$$

Let set $D$ be all possible ordered pairs using elements from $A$ and $B$, where the element of $A$ is first. If for each element $(k_1,k_2)$in set $D$ we return a value $\theta$ where:

$$\begin{gathered} \theta \equiv k_1\mathrm{mod}m \\ \theta \equiv k_2\mathrm{mod}n \end{gathered}$$

CRT ensures $\theta$ is unique to $\mathrm{mod}ab$ and exists. Given the fact $\gcd (x+yz,z)=\gcd (x,z)$, we can say that:

$$\begin{gathered} \gcd (\theta ,m)=\gcd (k_1,m)=1 \\ \gcd (\theta ,n)=\gcd (k_2,n)=1 \\ \gcd (\theta ,mn)=1 \end{gathered}$$

If we put all $\theta$ in set $C$, we can see that set $C$ has all the elements fitting the above conditions. Looking at the length of $C$:

$$\begin{gathered} |C|=\varphi (mn) \\ |C|=|A|\ast |B|=\varphi (m)\varphi (n) \\ \varphi (mn)=\varphi (m)\varphi (n) \end{gathered}$$

Value of $\varphi$ for any Number

Let a positive integer $n$ prime factorization be:

$$n=p_1^{k_1}{p}_2^{k_2}{p}_3^{k_3}...p_l^{k_l}$$

Now using the properties above:

$$\begin{gathered} \varphi (n) \\ =\prod _{i=1}^l\varphi (p_i^{k_i}) \\ =\prod _{i=1}^l{p}_i^{k_i}(1-\frac{1}{p_i}) \end{gathered}$$

Multiplying all $p_i^{k_i}$ gives $n$, so factor that out:

$$=n\prod _{i=1}^l(1-\frac{1}{p_i})$$

(you can derive most textbook definitions from this formula easily)

Final formula:

$$\varphi (n)=n\prod _{i=1}^l(1-\frac{1}{p_i})$$