Totient function: Difference between revisions
Jump to navigation
Jump to search
imported>Richard Pinch (corrected math markup) |
imported>Richard Pinch (added section on Euler's Theorem) |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
In [[number theory]], the '''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.<ref>William Dunham, ''Euler, the Master of us all'', MAA (1999) ISBN 0-8835-328-0. Pp.1-16.</ref> | ||
| Line 11: | Line 11: | ||
* <math>\sum_{d | n } \phi(d) = n \, </math>. | * <math>\sum_{d | n } \phi(d) = n \, </math>. | ||
* The [[Average order of an arithmetic function|average order]] of φ(''n'') is <math>\frac{6}{\pi^2} n</math>. | * The [[Average order of an arithmetic function|average order]] of φ(''n'') is <math>\frac{6}{\pi^2} n</math>. | ||
==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'')<sup>*</sup>. By Legendre's theorem, the multiplicative order of any element is a factor of φ(''n''): that is | |||
* <math>a^{\phi(n)} \equiv 1 \pmod n \,</math> if <math>a</math> is coprime to <math>n</math>. | |||
==References== | ==References== | ||
{{reflist}} | {{reflist}} | ||
* {{cite book | author=G.H. Hardy | authorlink=G. H. Hardy | coauthors=E.M. Wright | title=An Introduction to the Theory of Numbers | edition=6th ed. | publisher=[[Oxford University Press]] | pages=347-360 | year=2008 | isbn=0-19-921986-5 }} | * {{cite book | author=G.H. Hardy | authorlink=G. H. Hardy | coauthors=E.M. Wright | title=An Introduction to the Theory of Numbers | edition=6th ed. | publisher=[[Oxford University Press]] | pages=347-360 | year=2008 | isbn=0-19-921986-5 }} | ||
Revision as of 02:26, 30 October 2008
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.[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 Legendre's theorem, the multiplicative order of any element is a factor of φ(n): that is
- if is coprime to .
References
- ↑ William Dunham, Euler, the Master of us all, MAA (1999) ISBN 0-8835-328-0. Pp.1-16.
- 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.