Euler's totient function

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$ .

"φ(n)" redirects here. For other uses, see Phi. Not to be confused with Euler function.

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[edit]

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$ .

$a\mid b\implies \varphi (a)\mid \varphi (b)$

$m\mid \varphi (a^{m}-1)$

$\varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)$ $\varphi (mn)=\varphi (m)\varphi (n)\cdot {\frac {d}{\varphi (d)}}\quad {\text{where }}d=\operatorname {gcd} (m,n)$

$\varphi (\operatorname {lcm} (m,n))\cdot \varphi (\operatorname {gcd} (m,n))=\varphi (m)\cdot \varphi (n)$
Compare this to the formula ${\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n}$ (see ).

least common multiple

$φ (n)$ is even for $n \geq 3$ .
Moreover, if $n$ has $r$ distinct odd prime factors, $2 r | φ (n)$

For any $a > 1$ and $n > 6$ such that $4 ∤ n$ there exists an $l \geq 2 n$ such that $l | φ (a n - 1)$ .

${\frac {\varphi (n)}{n}}={\frac {\varphi (\operatorname {rad} (n))}{\operatorname {rad} (n)}}$
where $rad(n)$ is the (the product of all distinct primes dividing $n$ ).

radical of $n$

$\sum _{d\mid n}{\frac {\mu ^{2}(d)}{\varphi (d)}}={\frac {n}{\varphi (n)}}$

[21]

$\sum _{1\leq k\leq n-1 \atop gcd(k,n)=1}\!\!k={\tfrac {1}{2}}n\varphi (n)\quad {\text{for }}n>1$

$\sum _{k=1}^{n}\varphi (k)={\tfrac {1}{2}}\left(1+\sum _{k=1}^{n}\mu (k)\left\lfloor {\frac {n}{k}}\right\rfloor ^{2}\right)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)$ ( cited in^[23])

[22]

$\sum _{k=1}^{n}\varphi (k)={\frac {3}{\pi ^{2}}}n^{2}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)$ [Liu (2016)]

$\sum _{k=1}^{n}{\frac {\varphi (k)}{k}}=\sum _{k=1}^{n}{\frac {\mu (k)}{k}}\left\lfloor {\frac {n}{k}}\right\rfloor ={\frac {6}{\pi ^{2}}}n+O\left((\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)$

[22]

$\sum _{k=1}^{n}{\frac {k}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}n-{\frac {\log n}{2}}+O\left((\log n)^{\frac {2}{3}}\right)$

[24]

$\sum _{k=1}^{n}{\frac {1}{\varphi (k)}}={\frac {315\,\zeta (3)}{2\pi ^{4}}}\left(\log n+\gamma -\sum _{p{\text{ prime}}}{\frac {\log p}{p^{2}-p+1}}\right)+O\left({\frac {(\log n)^{\frac {2}{3}}}{n}}\right)$
(where $γ$ is the Euler–Mascheroni constant).

[24]

Carmichael function (λ)

Dedekind psi function (𝜓)

Divisor function (σ)

, Encyclopedia of Mathematics, EMS Press, 2001 [1994]

"Totient function"

Archived 2021-02-28 at the Wayback Machine

Euler's Phi Function and the Chinese Remainder Theorem — proof that $φ (n)$ is multiplicative

Euler's totient function calculator in JavaScript — up to 20 digits

Dineva, Rosica, Archived 2021-01-16 at the Wayback Machine

The Euler Totient, the Möbius, and the Divisor Functions

Plytage, Loomis, Polhill

Euler's totient function

History, terminology, and notation[edit]

least common multiple

radical of n

[21]

[22]

[22]

[24]

[24]

Carmichael function (λ)

Dedekind psi function (𝜓)

Divisor function (σ)

"Totient function"

Euler's Phi Function and the Chinese Remainder Theorem — proof that φ(n) is multiplicative

Euler's totient function calculator in JavaScript — up to 20 digits

The Euler Totient, the Möbius, and the Divisor Functions

Summing Up The Euler Phi Function

radical of $n$

Euler's Phi Function and the Chinese Remainder Theorem — proof that $φ (n)$ is multiplicative