Content deleted Content added
ClueBot NG (talk | contribs) m Reverting possible vandalism by SR71BIackBlrd to version by Anita5192. Report False Positive? Thanks, ClueBot NG. (4363190) (Bot) |
Undid revision 1306939706 by Mikhael Username (talk) since, in this context, log(x) is more common than ln(x). Adding the template {{log(x)}} |
||
| (23 intermediate revisions by 14 users not shown) | |||
Line 4:
{{distinguish|Euler function}}
}}
{{log(x)}}
[[Image:EulerPhi.svg|thumb|The first thousand values of {{math|''φ''(''n'')}}. The points on the top line represent {{Math|''φ''(''p'')}} when {{mvar|p}} is a prime number, which is {{Math|''p'' − 1.}}<ref>{{Cite web
| url = https://www.khanacademy.org/computing/computer-science/cryptography/modern-crypt/v/euler-s-totient-function-phi-function
Line 22 ⟶ 23:
[[Leonhard Euler]] introduced the function in 1763.<ref>L. Euler "[http://eulerarchive.maa.org/pages/E271.html Theoremata arithmetica nova methodo demonstrata]" (An arithmetic theorem proved by a new method), ''Novi commentarii academiae scientiarum imperialis Petropolitanae'' (New Memoirs of the Saint-Petersburg Imperial Academy of Sciences), '''8''' (1763), 74–104. (The work was presented at the Saint-Petersburg Academy on October 15, 1759. A work with the same title was presented at the Berlin Academy on June 8, 1758). Available on-line in: [[Ferdinand Rudio]], {{abbr|ed.|editor}}, ''Leonhardi Euleri Commentationes Arithmeticae'', volume 1, in: ''Leonhardi Euleri Opera Omnia'', series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915), [http://gallica.bnf.fr/ark:/12148/bpt6k6952c/f571.image pages 531–555]. On page 531, Euler defines {{mvar|n}} as the number of integers that are smaller than {{mvar|N}} and relatively prime to {{mvar|N}} (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), which is the phi function, φ(N).</ref><ref name="Sandifer, p. 203">Sandifer, p. 203</ref><ref>Graham et al. p. 133 note 111</ref> However, he did not at that time choose any specific symbol to denote it. In a 1784 publication, Euler studied the function further, choosing the Greek letter {{mvar|π}} to denote it: he wrote {{math|''πD''}} for "the multitude of numbers less than {{mvar|D}}, and which have no common divisor with it".<ref>L. Euler, ''[http://math.dartmouth.edu/~euler/docs/originals/E564.pdf Speculationes circa quasdam insignes proprietates numerorum]'', Acta Academiae Scientarum Imperialis Petropolitinae, vol. 4, (1784), pp. 18–30, or Opera Omnia, Series 1, volume 4, pp. 105–115. (The work was presented at the Saint-Petersburg Academy on October 9, 1775).</ref> This definition varies from the current definition for the totient function at {{math|1=''D'' = 1}} but is otherwise the same. The now-standard notation<ref name="Sandifer, p. 203"/><ref>Both {{math|''φ''(''n'')}} and {{math|''ϕ''(''n'')}} are seen in the literature. These are two forms of the lower-case Greek letter [[phi]].</ref> {{math|''φ''(''A'')}} comes from [[Gauss]]'s 1801 treatise ''[[Disquisitiones Arithmeticae]]'',<ref>Gauss, ''Disquisitiones Arithmeticae'' article 38</ref><ref>{{cite book |last=Cajori |first=Florian |author-link=Florian Cajori |title=A History Of Mathematical Notations Volume II |year=1929 |publisher=Open Court Publishing Company|at=§409}}</ref> although Gauss did not use parentheses around the argument and wrote {{math|''φA''}}. Thus, it is often called '''Euler's phi function''' or simply the '''phi function'''.
In 1879, [[James Joseph Sylvester|J. J. Sylvester]] coined the term '''totient''' for this function,<ref>J. J. Sylvester (1879) "On certain ternary cubic-form equations", ''American Journal of Mathematics'', '''2''' : 357-393; Sylvester coins the term "totient" on [https://books.google.com/books?id=-AcPAAAAIAAJ&pg=PA361 page 361].</ref><ref>{{cite OED2|totient}}</ref> so it is also referred to as '''Euler's totient function''', the '''Euler totient''', or '''Euler's totient'''.<ref>{{Cite web |last=Weisstein |first=Eric W. |title=Totient Function |url=https://mathworld.wolfram.com/TotientFunction.html |access-date=2025-02-09 |website=mathworld.wolfram.com |language=en}}</ref> [[Jordan's totient function|Jordan's totient]] is a generalization of Euler's.
The '''cototient''' of {{mvar|n}} is defined as {{math|''n'' − ''φ''(''n'')}}. It counts the number of positive integers less than or equal to {{mvar|n}} that have at least one [[prime number|prime factor]] in common with {{mvar|n}}.
Line 34 ⟶ 35:
It states
:<math>\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right),</math>
where the product is over the distinct [[prime number]]s dividing {{mvar|n}}.
An equivalent formulation is
Line 55 ⟶ 56:
====Proof of Euler's product formula====
The [[fundamental theorem of arithmetic]] states that if {{math|''n'' > 1}} there is a unique expression <math>n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}, </math> where {{math|''p''<sub>1</sub> < ''p''<sub>2</sub> < ... < ''p''<sub>''r''</sub>}} are [[prime number]]s and each {{math|''k''<sub>''i''</sub> ≥ 1}}. (The case {{math|1=''n'' = 1}} corresponds to the [[empty product]].) Repeatedly using the multiplicative property of {{mvar|φ}} and the formula for {{math|''φ''(''p''<sup>''k''</sup>)}} gives
:<math>\begin{array} {rcl}
Line 104 ⟶ 105:
&=& 4 .
\end{array}
</math>Unlike the [[Euler product]] and the divisor sum formula, this one does not require knowing the factors of {{mvar|n}}. However, it does involve the calculation of the greatest common divisor of {{mvar|n}} and every positive integer less than {{mvar|n}}, which suffices to provide the factorization anyway.
===Divisor sum===
Line 245 ⟶ 246:
===Divisibility by any fixed positive integer===
The following property, which is part of the « folklore » (i.e., apparently unpublished as a specific result:<ref> {{citation | last = Pollack | first = P. | title = Two problems on the distribution of Carmichael's lambda function | journal = Mathematika | year = 2023 | volume = 69 | issue = 4| pages = 1195–1220 | doi = 10.1112/mtk.12222
| url = | doi-access = free | arxiv = 2303.14043 }}</ref> see the introduction of this article in which it is stated as having « long been known ») has important consequences. For instance it rules out uniform distribution of the values of <math>\varphi(n)</math> in the arithmetic progressions modulo <math>q</math> for any integer <math>q>1</math>.
Line 339 ⟶ 340:
is dense in the interval (0,1).
==Totient
A '''totient number''' is a value of Euler's totient function: that is, an {{mvar|m}} for which there is at least one {{mvar|n}} for which {{math|''φ''(''n'') {{=}} ''m''}}. The ''valency'' or ''multiplicity'' of a totient number {{mvar|m}} is the number of solutions to this equation.<ref name=Guy144>Guy (2004) p.144</ref> A ''[[nontotient]]'' is a natural number which is not a totient number. Every odd integer exceeding 1 is trivially a nontotient. There are also infinitely many even nontotients,<ref name=SC230>Sándor & Crstici (2004) p.230</ref> and indeed every positive integer has a multiple which is an even nontotient.<ref name=Zha1993>{{cite journal | zbl=0772.11001 | last=Zhang | first=Mingzhi | title=On nontotients | journal=[[Journal of Number Theory]] | volume=43 | number=2 | pages=168–172 | year=1993 | issn=0022-314X | doi=10.1006/jnth.1993.1014| doi-access=free }}</ref>
Line 346 ⟶ 347:
:<math>\frac{x}{\log x}e^{ \big(C+o(1)\big)(\log\log\log x)^2 } </math>
for a constant {{math|''C'' {{=}} 0.8178146...}}.<ref name=Ford1998>{{cite journal | zbl=0914.11053 | last=Ford | first=Kevin | title=The distribution of totients | journal=Ramanujan J.
If counted accordingly to multiplicity, the number of totient numbers up to a given limit {{mvar|x}} is
Line 414 ⟶ 415:
===Riemann hypothesis===
The [[Riemann hypothesis]] is true [[if and only if]] the inequality
:<math>\frac{n}{\varphi (n)}<e^\gamma \log\log n+\frac{e^\gamma (4+\gamma-\log 4\pi)}{\sqrt{\log n}}</math>
is true for all {{math|''n'' ≥ ''p''<sub>120569</sub>#}} where {{mvar|γ}} is [[Euler's constant]] and {{math|''p''<sub>120569</sub>#}} is the [[Primorial|product of the first]] {{math|120569}} primes.<ref>{{Cite book |last1=Broughan |first1=Kevin |title=Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents |publisher=Cambridge University Press |year=2017 |edition=First |isbn=978-1-107-19704-6}} Corollary 5.35</ref>
Line 422 ⟶ 423:
*[[Dedekind psi function|Dedekind psi function (𝜓)]]
*[[Divisor function|Divisor function (σ)]]
*[[Duffin–Schaeffer conjecture]]
*[[Fermat's little theorem#Generalizations|Generalizations of Fermat's little theorem]]
*[[Highly composite number]]
*[[Multiplicative group of integers modulo n|Multiplicative group of integers modulo {{mvar|n}}]]
*[[Ramanujan sum]]
Line 522 ⟶ 521:
| volume = 146
| issue = 4
| year = 2016
| doi = 10.1017/S0308210515000682
}}.
* {{citation | first1 = Calvin T. | last1 = Long | year = 1972 | title = Elementary Introduction to Number Theory | edition = 2nd | publisher = [[D. C. Heath and Company]] | ___location = Lexington | lccn = 77-171950 }}
* {{citation | first1 = Anthony J. | last1 = Pettofrezzo | first2 = Donald R. | last2 = Byrkit | year = 1970 | title = Elements of Number Theory | publisher = [[Prentice Hall]] | ___location = Englewood Cliffs | lccn = 77-81766 }}
| |||