Totient function

(Redirected from Euler's totient function)

Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
Citable Version  [?]

This editable Main Article is under development and subject to a disclaimer.

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

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

Properties

• ${\displaystyle \sum _{d|n}\phi (d)=n\,}$.
• The average order of φ(n) is ${\displaystyle {\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

• ${\displaystyle a^{\phi (n)}\equiv 1{\pmod {n}}\,}$ if ${\displaystyle a}$ is coprime to ${\displaystyle n}$.

References

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