kidzsearch.com > wiki Explore:web images videos games

# Euler's totient function

In number theory, the **totient** of a positive integer *n* is the number of positive integers smaller than *n* which are coprime to *n* (they share no factors except 1). It is often written as [math]\phi (n)[/math].

For example, [math]\phi(8) = 4[/math], because there are four numbers (1, 3, 5 and 7) which do not share any factors with 8.
The function [math]\phi[/math] used here is the **totient function**,^{[1]}^{[2]} usually called the **Euler totient** or **Euler's totient**, after the Swiss mathematician Leonhard Euler, who studied it.
The totient function is also called **Euler's phi function** or simply the **phi function**,^{[3]} since the Greek letter Phi ([math]\phi[/math]) is so commonly used for it. The **cototient** of *n* is defined as [math]n - \phi(n)[/math].

The totient function is important mainly because it gives the size of the multiplicative group of integers modulo *n*. More precisely, [math]\phi(n)[/math] is the order of the group of units of the ring [math]\mathbb{Z}/n\mathbb{Z}[/math]. This fact, together with Lagrange's theorem, provides a proof for Euler's theorem.

A common use of the totient function is in the RSA algorithm. The RSA algorithm is a popular method of encryption used worldwide.

For any prime number, *p*, [math]\phi(p) = p-1[/math].

## Related pages

## References

- ↑ "Comprehensive List of Algebra Symbols" (in en-US). 2020-03-25. https://mathvault.ca/hub/higher-math/math-symbols/algebra-symbols/.
- ↑ Weisstein, Eric W.. "Totient Function" (in en). https://mathworld.wolfram.com/TotientFunction.html.
- ↑ "Euler's Totient Function and Euler's Theorem". https://www.doc.ic.ac.uk/~mrh/330tutor/ch05s02.html.