Totient function: Difference between revisions
Jump to navigation
Jump to search
imported>Richard Pinch (added section on Euler's Theorem) |
mNo edit summary |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
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> | 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.<ref>William Dunham, ''Euler, the Master of us all'', MAA (1999) ISBN 0-8835-328-0. Pp.1-16.</ref> | ||
| Line 13: | Line 13: | ||
==Euler's Theorem== | ==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 | 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 (group theory)|order]] of ('''Z'''/''n'')<sup>*</sup>. By [[Lagrange'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>. | * <math>a^{\phi(n)} \equiv 1 \pmod n \,</math> if <math>a</math> is coprime to <math>n</math>. | ||
| Line 20: | Line 20: | ||
{{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 }} | ||
[[Category:Suggestion Bot Tag]] | |||
Latest revision as of 16:01, 29 October 2024
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
- ↑ 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.