Definition:Euler Phi Function

From ProofWiki
Jump to navigation Jump to search

Definition

Let $n \in \Z_{>0}$, that is, a strictly positive integer.


The Euler $\phi$ (phi) function is the arithmetic function $\phi: \Z_{>0} \to \Z_{>0}$ defined as:

$\map \phi n = $ the number of strictly positive integers less than or equal to $n$ which are prime to $n$


That is:

$\map \phi n = \card {S_n}: S_n = \set {k: 1 \le k \le n, k \perp n}$


That is, the number of totitives to $n$.


Examples

The values of the Euler $\phi$ function for the first few integers are as follows:

$n$ $\map \phi n$ $m$ not coprime: $1 \le m \le n$
$1$ $1$ $\O$
$2$ $1$ $2$
$3$ $2$ $3$
$4$ $2$ $2, 4$
$5$ $4$ $5$
$6$ $2$ $2, 3, 4, 6$
$7$ $6$ $7$
$8$ $4$ $2, 4, 6, 8$
$9$ $6$ $3, 6, 9$
$10$ $4$ $2, 4, 5, 6, 8, 10$


Also known as

The Euler $\phi$ function is also known as:

the totient function
the Euler totient function.


It is also variously rendered:

with a hyphen: Euler $\phi$-function
in the possessive form: Euler's $\phi$ function
merely as Euler's function
the $\phi$ function


The symbol $\map \varphi n$ can sometimes be seen.


Some sources use the term indicator function, but this has more than one use, and so is discouraged on $\mathsf{Pr} \infty \mathsf{fWiki}$.


Also see

  • Results about the Euler $\phi$ function can be found here.


Source of Name

This entry was named for Leonhard Paul Euler.


Historical Note

The Euler $\phi$ function was invented by Leonhard Paul Euler in $1760$ in order to generalise Fermat's Little Theorem to non-prime indices.


Linguistic Note

The word totient is pronounced to rhyme with quotient, that is: toe-shyent or toe-shent, according to taste.

The same applies to its various relatives: nontotient, cototient, noncototient, and so on.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Euler_Phi_Function&oldid=736499"