# Totient function

From Citizendium

In number theory, the **totient function** or **Euler's φ function** of a positive integer *n*, denoted φ(*n*), is defined to be the number of positive integers in the set {1,...,*n*} which are coprime to *n*. This function was studied by Leonhard Euler around 1730.^{[1]}

## Definition

The totient function is multiplicative and may be evaluated as

## Properties

- .
- The average order of φ(
*n*) is .

## Euler's Theorem

The integers in the set {1,...,*n*} which are coprime to *n* represent the multiplicative group modulo *n* and hence the totient function of *n* is the order of (**Z**/*n*)^{*}. By Lagrange's theorem, the multiplicative order of any element is a factor of φ(*n*): that is

- if is coprime to .

## References

- ↑ William Dunham,
*Euler, the Master of us all*, MAA (1999) ISBN 0-8835-328-0. Pp.1-16.

- G.H. Hardy; E.M. Wright (2008).
*An Introduction to the Theory of Numbers*, 6th ed.. Oxford University Press, 347-360. ISBN 0-19-921986-5.