Euler's totient function

The first thousand values of $φ (n)$ . The points on the top line represent $φ (p)$ when $p$ is a prime number, which is $p - 1.$ ^[1]

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

For example, the totatives of $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 $gcd(9, 3) = gcd(9, 6) = 3$ and $gcd(9, 9) = 9$ . Therefore, $φ (9) = 6$ . As another example, $φ (1) = 1$ since for $n = 1$ the only integer in the range from 1 to $n$ is 1 itself, and $gcd(1, 1) = 1$ .

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

History, terminology, and notation

Leonhard Euler introduced the function in 1763.^[7]^[8]^[9] However, he did not at that time choose any specific symbol to denote it. In a 1784 publication, Euler studied the function further, choosing the Greek letter $π$ to denote it: he wrote $πD$ for "the multitude of numbers less than $D$ , and which have no common divisor with it".^[10] This definition varies from the current definition for the totient function at $D = 1$ but is otherwise the same. The now-standard notation^[8]^[11] $φ (A)$ comes from Gauss's 1801 treatise Disquisitiones Arithmeticae,^[12]^[13] although Gauss did not use parentheses around the argument and wrote $φA$ . Thus, it is often called Euler's phi function or simply the phi function.

In 1879, J. J. Sylvester coined the term totient for this function,^[14]^[15] so it is also referred to as Euler's totient function, the Euler totient, or Euler's totient. Jordan's totient is a generalization of Euler's.

The cototient of $n$ is defined as $n - φ (n)$ . It counts the number of positive integers less than or equal to $n$ that have at least one prime factor in common with $n$ .

Computing Euler's totient function

There are several formulae for computing $φ (n)$ .

Euler's product formula

It states

\varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),

where the product is over the distinct prime numbers dividing $n$ . (For notation, see Arithmetical function.)

An equivalent formulation is

\varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1),

where

n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}

is the prime factorization of

n

(that is,

p_{1},p_{2},\ldots ,p_{r}

are distinct prime numbers).

The proof of these formulae depends on two important facts.

Phi is a multiplicative function

This means that if $gcd(m, n) = 1$ , then $φ (m) φ (n) = φ (mn)$ . Proof outline: Let $A$ , $B$ , $C$ be the sets of positive integers which are coprime to and less than $m$ , $n$ , $mn$ , respectively, so that $| A | = φ (m)$ , etc. Then there is a bijection between $A \times B$ and $C$ by the Chinese remainder theorem.

Value of phi for a prime power argument

If $p$ is prime and $k \geq 1$ , then

\varphi \left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\tfrac {1}{p}}\right).

Proof: Since $p$ is a prime number, the only possible values of $gcd(p k, m)$ are $1, p, p 2, ..., p k$ , and the only way to have $gcd(p k, m) > 1$ is if $m$ is a multiple of $p$ , that is, $m \in {p, 2 p, 3 p, ..., p k - 1 p = p k}$ , and there are $p k - 1$ such multiples not greater than $p k$ . Therefore, the other $p k - p k - 1$ numbers are all relatively prime to $p k$ .

Proof of Euler's product formula

The fundamental theorem of arithmetic states that if $n > 1$ there is a unique expression $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},$ where $p 1 < p 2 < ... < p r$ are prime numbers and each $k i \geq 1$ . (The case $n = 1$ corresponds to the empty product.) Repeatedly using the multiplicative property of $φ$ and the formula for $φ (p k)$ gives