Editing Euler's totient function (section)

==Growth rate==

In the words of Hardy & Wright, the order of {{math|''φ''(''n'')}} is "always 'nearly {{mvar|n}}'."<ref>{{harvnb|Hardy|Wright|1979|loc=intro to § 18.4}}</ref>

First<ref>{{harvnb|Hardy|Wright|1979|loc=thm. 326}}</ref>

:<math>\lim\sup \frac{\varphi(n)}{n}= 1,</math>

but as ''n'' goes to infinity,<ref>{{harvnb|Hardy|Wright|1979|loc=thm. 327}}</ref> for all {{math|''δ'' > 0}}

:<math>\frac{\varphi(n)}{n^{1-\delta}}\rightarrow\infty.</math>

These two formulae can be proved by using little more than the formulae for {{math|''φ''(''n'')}} and the [[divisor function|divisor sum function]] {{math|''σ''(''n'')}}.

In fact, during the proof of the second formula, the inequality

:<math>\frac {6}{\pi^2} < \frac{\varphi(n) \sigma(n)}{n^2} < 1,</math>

true for {{math|''n'' > 1}}, is proved.

We also have<ref name="hw328">{{harvnb|Hardy|Wright|1979|loc=thm. 328}}</ref>

:<math>\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma}.</math>

Here {{mvar|γ}} is [[Euler–Mascheroni constant|Euler's constant]], {{math|''γ'' {{=}} 0.577215665...}}, so {{math|''e<sup>γ</sup>'' {{=}} 1.7810724...}} and {{math|''e''<sup>−''γ''</sup> {{=}} 0.56145948...}}.

Proving this does not quite require the [[prime number theorem]].<ref>In fact Chebyshev's theorem ({{harvnb|Hardy|Wright|1979|loc=thm.7}}) and
Mertens' third theorem is all that is needed.</ref><ref>{{harvnb|Hardy|Wright|1979|loc=thm. 436}}</ref> Since {{math|log log ''n''}} goes to infinity, this formula shows that

:<math>\lim\inf\frac{\varphi(n)}{n}= 0.</math>

In fact, more is true.<ref>Theorem 15 of {{cite journal|last1=Rosser |first1=J. Barkley |last2=Schoenfeld |first2=Lowell |title=Approximate formulas for some functions of prime numbers |journal=Illinois J. Math. |volume=6 |date=1962 |issue=1 |pages=64–94 |doi=10.1215/ijm/1255631807 |url=http://projecteuclid.org/euclid.ijm/1255631807|doi-access=free }}</ref><ref>Bach & Shallit, thm. 8.8.7</ref><ref name=Rib320>{{cite book|last=Ribenboim|title=The Book of Prime Number Records |edition=2nd |publisher=Springer-Verlag |location=New York |chapter=How are the Prime Numbers Distributed? §I.C The Distribution of Values of Euler's Function |pages=172–175 |doi= 10.1007/978-1-4684-0507-1_5 |date=1989 |isbn=978-1-4684-0509-5 }}</ref>

:<math>\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}} \quad\text{for } n>2</math>

and

:<math>\varphi(n) < \frac {n} {e^{ \gamma}\log \log n} \quad\text{for infinitely many } n.</math>

The second inequality was shown by [[Jean-Louis Nicolas]]. Ribenboim says "The method of proof is interesting, in that the inequality is shown first under the assumption that the [[Riemann hypothesis]] is true, secondly under the contrary assumption."<ref name=Rib320/>{{rp|173}}

For the average order, we have<ref name=Wal1963/><ref name=SMC2425>Sándor, Mitrinović & Crstici (2006) pp.24–25</ref>

:<math>\varphi(1)+\varphi(2)+\cdots+\varphi(n) = \frac{3n^2}{\pi^2}+O\left(n(\log n)^\frac23(\log\log n)^\frac43\right) \quad\text{as }n\rightarrow\infty,</math>
due to [[Arnold Walfisz]], its proof exploiting estimates on exponential sums due to [[Ivan Matveevich Vinogradov|I. M. Vinogradov]] and [[N. M. Korobov]]. 
By a combination of van der Corput's and Vinogradov's methods, H.-Q. Liu (On Euler's function.Proc. Roy. Soc. Edinburgh Sect. A 146 (2016), no. 4, 769–775)  
improved the error term to 
:<math>
O\left(n(\log n)^\frac23(\log\log n)^\frac13\right) 
</math>
(this is currently the best known estimate of this type). The [[Big O notation|"Big {{mvar|O}}"]] stands for a quantity that is bounded by a constant times the function of {{mvar|n}} inside the parentheses (which is small compared to {{math|''n''<sup>2</sup>}}).

This result can be used to prove<ref>{{harvnb|Hardy|Wright|1979|loc=thm. 332}}</ref> that [[Coprime integers#Probability of coprimality|the probability of two randomly chosen numbers being relatively prime]] is {{sfrac|6|{{pi}}<sup>2</sup>}}.