# Totient function  Main Article Discussion Related Articles  [?] Bibliography  [?] External Links  [?] Citable Version  [?] This editable Main Article is under development and subject to a disclaimer. [edit intro]

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.

## 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 Lagrange'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$ .