Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer ${\displaystyle n}$ that are relatively prime to ${\displaystyle n}$. It is written using the Greek letter phi as ${\displaystyle \varphi (n)}$ or ${\displaystyle \phi (n)}$, and may also be called Euler's phi function. In other words, it is the number of integers ${\displaystyle k}$ in the range ${\displaystyle 1\leq k\leq n}$ for which the greatest common divisor ${\displaystyle \gcd(n,k)}$ is equal to 1. The integers ${\displaystyle k}$ of this form are sometimes referred to as totatives of ${\displaystyle n}$.

For example, the totatives of ${\displaystyle n=9}$ are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, since ${\displaystyle \gcd(9,3)=\gcd(9,6)=3}$ and ${\displaystyle \gcd(9,9)=9}$. Therefore, ${\displaystyle \varphi (9)=6}$. As another example, ${\displaystyle \varphi (1)=1}$ since for ${\displaystyle n=1}$ the only integer in the range from 1 to ${\displaystyle n}$ is 1 itself, and ${\displaystyle \gcd(1,1)=1}$.

Euler's totient function is a multiplicative function, meaning that if two numbers ${\displaystyle m}$ and ${\displaystyle n}$ are relatively prime, then ${\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}$. This function gives the order of the multiplicative group of integers modulo n (the group of units of the ring ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$). It is also used for defining the RSA encryption system.