Euler's Totient Function - Growth of The Function

Growth of The Function

In the words of Hardy & Wright, φ(n) is "always ‘nearly n’."

First

\lim\sup \frac{\varphi(n)}{n}= 1,

but as n goes to infinity, for all δ > 0

\frac{\varphi(n)}{n^{1-\delta}}\rightarrow\infty.

These two formulae can be proved by using little more than the formulae for φ(n) and the divisor sum function σ(n).
In fact, during the proof of the second formula, the inequality

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

true for n > 1, is proven.
We also have

\lim\inf\frac{\varphi(n)}{n}\log\log n = e^{-\gamma}. Here γ is Euler's constant, γ = 0.577215665..., eγ = 1.7810724..., e−γ = 0.56145948... .

Proving this, however, requires the prime number theorem. Since log log (n) goes to infinity, this formula shows that

\lim\inf\frac{\varphi(n)}{n}= 0.

In fact, more is true.

\varphi(n) > \frac {n} {e^\gamma\; \log \log n + \frac {3} {\log \log n}} for n > 2, and
\varphi(n) < \frac {n} {e^{ \gamma}\log \log n} for infinitely many n.

Concerning the second inequality, 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."

For the average order we have

\varphi(1)+\varphi(2)+\cdots+\varphi(n) = \frac{3n^2}{\pi^2}+\mathcal{O} (n\log n)

The "Big O" stands for a quantity that is bounded by a constant times nlog n (which is small compared to n2).

This result can be used to prove that the probability of two randomly-chosen numbers being relatively prime is

Read more about this topic:  Euler's Totient Function

Famous quotes containing the words growth of the, growth of, growth and/or function:

    “You know that the nucleus of a time is not
    The poet but the poem, the growth of the mind
    Of the world, the heroic effort to live expressed
    As victory. The poet does not speak in ruins
    Nor stand there making orotund consolations.
    He shares the confusions of intelligence.”
    —Wallace Stevens (1879–1955)

    “The wind of change is blowing through the continent. Whether we like it or not, this growth of national consciousness is a political fact.”
    —Harold MacMillan (1894–1986)

    “Next to the right of liberty, the right of property is the most important individual right guaranteed by the Constitution and the one which, united with that of personal liberty, has contributed more to the growth of civilization than any other institution established by the human race.”
    —William Howard Taft (1857–1930)

    “Morality and its victim, the mother—what a terrible picture! Is there indeed anything more terrible, more criminal, than our glorified sacred function of motherhood?”
    —Emma Goldman (1869–1940)