Editing Euler's totient function (section)

== History, terminology, and notation ==

[[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&nbsp;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}}.