Euler's totient function: Difference between revisions

Revision as of 10:01, 18 July 2025

Latest revision as of 16:04, 20 August 2025

(3 intermediate revisions by 3 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 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''₁ < ''p''₂ < ... < ''p''_''r''}} are [[prime number]]s and each {{math|''k''_''i'' ≥ 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''^''k'')}} 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 147 ⟶ 148:

\end{align}

</math>

== Patterns in {{math|''φ''(''n'')}} and {{math|''φ''(''n'')/''n''}} ==

[[File:Euler phin 1e4 all.svg|thumb|right|Scatter plot of the Euler Totient function <math> \varphi(n) </math> for the numbers up to 10,000. Prime numbers are on the upper line of slope ~ 1.]]

[[File:Euler phin 1e7 5pcent.svg|thumb|right|Scatter plot of the Euler Totient function <math> \varphi(n) </math> for the numbers up to 1E7. Prime numbers are on the upper line of slope ~ 1. Five percent of the numbers are randomly selected to get a better plot.]]

[[File:Euler phin overn plot.svg|thumb|right|Scatter plot of the Euler totient function <math> \varphi(n)/n </math> with the small prime factors accounting for the accumulation of points on nearly horizontal lines.]]

[[File:Euler phin overn histo.svg|thumb|right|Histogram of <math> \varphi(n)/n </math> for {{ math| ''n'' ≤ }} 1E7, showing the spectra-like pattern with a few prominent lines related to numbers with small prime factors and a single large prime factor.]]

In the plots showing <math> \varphi(n)</math> there are obvious patterns with more or less regular lines and concentration of points on special slopes. The feature appears very early and is already fully developed with <math> n < 10,000 </math> and conspicuous at larger values. While it shows up as slopes in <math> \varphi(n) </math> it comes as nearly horizontal lines in the plots of <math> \varphi(n)/n </math>, with obvious higher density of points at simple numbers like {{math| 1/3, 1/2, 2/3, 4/5}}. Even more striking is the histogram of <math> \varphi(n)/n </math> which looks like a periodogram or a spectrum of a physical phenomenon.

While this looks somewhat complex the explanation is simple and accounts for all the details. We know that,

:<math> \frac{\varphi(n)}{n} = \frac{p_1-1}{p_1}\frac{p_2-1}{p_2} \cdots \frac{p_r-1}{p_r} </math>

and this holds for any integer, whatever the power <math> p_r^{\alpha_r} </math> of the primes in the prime decomposition. Therefore all the prime numbers <math> n= p </math>, or the simple power of a prime number like <math> n= p^\alpha </math> lead to

:<math> \frac{\varphi(n)}{n} = \frac{p-1}{p} </math>

which approaches quickly one with increasing ''p''. These numbers cluster on the line of slope 1 in the plots of <math> \varphi(n) </math> and along the top horizontal line in the plots for <math> \varphi(n)/n </math>.

Now many numbers <math> n </math> factor with a few small prime factors and a single much larger prime number. A few examples are <math> 8856995 = 5\times 7 \times 36151 </math>, <math> 9502803 = 3^2 \times 1,055,867</math>, <math> 9098763 = 3 \times 3,032,921</math> or a last one <math> 9759450 = 2 \times 3 \times 5^2 \times 65,063</math>. All these numbers yields for <math> \frac{\varphi(n)}{n} </math> simple fractions like <math> 4/5\times 6/7, 2/3, 1/2\times 2/3 \times 4/5 </math> multiplied by a fraction <math> (p-1)/p \approx 1 </math> where <math> p </math> is a large prime. These fractions are seen in the plots as near horizontal lines with large concentration of numbers or as vertical lines in the spectrum-like plot. The list of small primes originating the pattern is indicated on the right of the horizontal line or on the top of the corresponding spectral lines. For example <math> \{3,7, p \gg 1\} </math> means a number with prime decomposition as <math> n = 3^\alpha 7^\beta p </math> where <math> p </math> is a large prime. In these cases we have with a good approximation

:<math> \frac{\varphi(n)}{n} = \frac{4}{7} </math>.

Similarly in the spectrum-like plot the <math> \{2,3,5, p \gg 1\} </math> is associated with the fractions very close to

:<math> \frac{\varphi(n)}{n} = \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = \frac{4}{15} \approx 0.2666 </math>.

==Some values==

Line 444 ⟶ 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''₁₂₀₅₆₉#}} where {{mvar|γ}} is [[Euler's constant]] and {{math|''p''₁₂₀₅₆₉#}} 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>