Totient function

In number theory, the totient 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.

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

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 Legendre's theorem, the multiplicative order of any element is a factor of φ(n): that is

• $a^{\phi (n)}\equiv 1{\pmod {n}}\,$ if $a$ is coprime to $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.