Totient function: Difference between revisions
Jump to navigation
Jump to search
imported>Richard Pinch (new entry, just a stub) |
imported>Richard Pinch (corrected math markup) |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
In [[number theory]], the '''totient function''' | In [[number theory]], the '''totient function''' φ(''n'') of a [[positive integer]] ''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> | ||
Revision as of 16:48, 29 October 2008
In number theory, the totient function φ(n) of a positive integer 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 .
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.