Totient function

In number theory, the totient function φ(n) of a positive integer 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.

Definition

The totient function is multiplicative and may be evaluated as

$\phi (n)=n\prod _{p|n}\left(1-{\frac {1}{p}}\right).\,$

Properties

• $\sum _{d|n}\phi (d)=n\,$.
• The average order of φ(n) is ${\frac {6}{\pi ^{2}}}n$.

References

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