Totient function

From Citizendium
Revision as of 17:35, 21 November 2008 by imported>Richard Pinch (alternative names; correct eponym)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
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

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

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