Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Euler's totient function

From Wikipedia, the free encyclopedia
(Redirected fromEuler totient function)
Number of integers coprime to and less than n
"φ(n)" redirects here. For other uses, seePhi.Not to be confused withEuler function.
This article uses technical mathematical notation for logarithms. All instances oflog(x) without a subscript base should be interpreted as anatural logarithm, also commonly written asln(x) orloge(x).
The first thousand values ofφ(n). The points on the top line representφ(p) whenp is a prime number, which isp − 1.[1]

Innumber theory,Euler's totient function counts the positive integers up to a given integern{\displaystyle n} that arerelatively prime ton{\displaystyle n}. It is written using the Greek letterphi asφ(n){\displaystyle \varphi (n)} orϕ(n){\displaystyle \phi (n)}, and may also be calledEuler's phi function. In other words, it is the number of integersk{\displaystyle k} in the range1≤k≤n{\displaystyle 1\leq k\leq n} for which thegreatest common divisorgcd(n,k){\displaystyle \gcd(n,k)} is equal to 1.[2][3] The integersk{\displaystyle k} of this form are sometimes referred to astotatives ofn{\displaystyle n}.

For example, the totatives ofn=9{\displaystyle n=9} are the six numbers 1, 2, 4, 5, 7 and 8. They are all relatively prime to 9, but the other three numbers in this range, 3, 6, and 9 are not, sincegcd(9,3)=gcd(9,6)=3{\displaystyle \gcd(9,3)=\gcd(9,6)=3} andgcd(9,9)=9{\displaystyle \gcd(9,9)=9}. Therefore,φ(9)=6{\displaystyle \varphi (9)=6}. As another example,φ(1)=1{\displaystyle \varphi (1)=1} since forn=1{\displaystyle n=1} the only integer in the range from 1 ton{\displaystyle n} is 1 itself, andgcd(1,1)=1{\displaystyle \gcd(1,1)=1}.

Euler's totient function is amultiplicative function, meaning that if two numbersm{\displaystyle m} andn{\displaystyle n} are relatively prime, thenφ(mn)=φ(m)φ(n){\displaystyle \varphi (mn)=\varphi (m)\varphi (n)}.[4][5]This function gives theorder of themultiplicative group of integers modulon (thegroup ofunits of theringZ/nZ{\displaystyle \mathbb {Z} /n\mathbb {Z} }).[6] It is also used for defining theRSA encryption system.

History, terminology, and notation

[edit]

Leonhard Euler introduced the function in 1763.[7][8][9] 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π{\displaystyle \pi } to denote it: he wroteπD{\displaystyle \pi D} for "the multitude of numbers less thanD{\displaystyle D}, and which have no common divisor with it".[10] This definition varies from the current definition for the totient function atD=1{\displaystyle D=1} but is otherwise the same. The now-standard notation[8][11]φ(A){\displaystyle \varphi (A)} comes fromGauss's 1801 treatiseDisquisitiones Arithmeticae,[12][13] although Gauss did not use parentheses around the argument and wroteφA{\displaystyle \varphi A}. Thus, it is often calledEuler's phi function or simply thephi function.

In 1879,J. J. Sylvester coined the termtotient for this function,[14][15] so it is also referred to asEuler's totient function, theEuler totient, orEuler's totient.[16]Jordan's totient is a generalization of Euler's.

Thecototient ofn{\displaystyle n} is defined asn−φ(n){\displaystyle n-\varphi (n)}. It counts the number of positive integers less than or equal ton{\displaystyle n} that have at least oneprime factor in common withn{\displaystyle n}.

Computing Euler's totient function

[edit]

There are several formulae for computingφ(n){\displaystyle \varphi (n)}.

Euler's product formula

[edit]

It states

φ(n)=n∏p∣n(1−1p),{\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),}

where the product is over the distinctprime numbers dividingn.

An equivalent formulation is

φ(n)=p1k1−1(p1−1)p2k2−1(p2−1)⋯prkr−1(pr−1),{\displaystyle \varphi (n)=p_{1}^{k_{1}-1}(p_{1}{-}1)\,p_{2}^{k_{2}-1}(p_{2}{-}1)\cdots p_{r}^{k_{r}-1}(p_{r}{-}1),}

wheren=p1k1p2k2⋯prkr{\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}} is theprime factorization ofn{\displaystyle n} (that is,p1,p2,…,pr{\displaystyle p_{1},p_{2},\ldots ,p_{r}} are distinct prime numbers).

The proof of these formulae depends on two important facts.

Phi is a multiplicative function

[edit]

This means that ifgcd(m,n)=1{\displaystyle \gcd(m,n)=1}, thenφ(m)φ(n)=φ(mn){\displaystyle \varphi (m)\varphi (n)=\varphi (mn)}.Proof outline: LetA,B,C{\displaystyle A,B,C} be the sets of positive integers which arecoprime to and less thanm,n,mn, respectively, so that|A|=φ(m){\displaystyle |A|=\varphi (m)}, etc. Then there is abijection betweenA×B{\displaystyle A\times B} andC by theChinese remainder theorem.

Value of phi for a prime power argument

[edit]

Ifp is prime andk≥1{\displaystyle k\geq 1}, then

φ(pk)=pk−pk−1=pk−1(p−1)=pk(1−1p).{\displaystyle \varphi \left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}(p-1)=p^{k}\left(1-{\tfrac {1}{p}}\right).}

Proof: Sincep is a prime number, the only possible values ofgcd(pk,m){\displaystyle \gcd(p^{k},m)} are1,p,p2,…,pk{\displaystyle 1,p,p^{2},\dots ,p^{k}}, and the only way to havegcd(pk,m)>1{\displaystyle \gcd(p^{k},m)>1} is ifm is a multiple ofp, that is,m∈{p,2p,3p,…,pk−1p=pk}{\displaystyle m\in \{p,2p,3p,\ldots ,p^{k-1}p=p^{k}\}}, and there arepk−1{\displaystyle p^{k-1}} such multiples not greater thanpk{\displaystyle p^{k}}. Therefore, the otherpk−pk−1{\displaystyle p^{k}-p^{k-1}} numbers are all relatively prime topk{\displaystyle p^{k}}.

Proof of Euler's product formula

[edit]

Thefundamental theorem of arithmetic states that ifn > 1 there is a unique expressionn=p1k1p2k2⋯prkr,{\displaystyle n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}},} wherep1 <p2 < ... <pr areprime numbers and eachki ≥ 1. (The casen = 1 corresponds to theempty product.) Repeatedly using the multiplicative property ofφ and the formula forφ(pk) gives

φ(n)=φ(p1k1)φ(p2k2)⋯φ(prkr)=p1k1(1−1p1)p2k2(1−1p2)⋯prkr(1−1pr)=p1k1p2k2⋯prkr(1−1p1)(1−1p2)⋯(1−1pr)=n(1−1p1)(1−1p2)⋯(1−1pr).{\displaystyle {\begin{array}{rcl}\varphi (n)&=&\varphi (p_{1}^{k_{1}})\,\varphi (p_{2}^{k_{2}})\cdots \varphi (p_{r}^{k_{r}})\\[.1em]&=&p_{1}^{k_{1}}\left(1-{\frac {1}{p_{1}}}\right)p_{2}^{k_{2}}\left(1-{\frac {1}{p_{2}}}\right)\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right)\\[.1em]&=&n\left(1-{\frac {1}{p_{1}}}\right)\left(1-{\frac {1}{p_{2}}}\right)\cdots \left(1-{\frac {1}{p_{r}}}\right).\end{array}}}

This gives both versions of Euler's product formula.

An alternative proof that does not require the multiplicative property instead uses theinclusion-exclusion principle applied to the set{1,2,…,n}{\displaystyle \{1,2,\ldots ,n\}}, excluding the sets of integers divisible by the prime divisors.

Example

[edit]
φ(20)=φ(225)=20(1−12)(1−15)=20⋅12⋅45=8.{\displaystyle \varphi (20)=\varphi (2^{2}5)=20\,(1-{\tfrac {1}{2}})\,(1-{\tfrac {1}{5}})=20\cdot {\tfrac {1}{2}}\cdot {\tfrac {4}{5}}=8.}

In words: the distinct prime factors of 20 are 2 and 5; half of the twenty integers from 1 to 20 are divisible by 2, leaving ten; a fifth of those are divisible by 5, leaving eight numbers coprime to 20; these are: 1, 3, 7, 9, 11, 13, 17, 19.

The alternative formula uses only integers:φ(20)=φ(2251)=22−1(2−1)51−1(5−1)=2⋅1⋅1⋅4=8.{\displaystyle \varphi (20)=\varphi (2^{2}5^{1})=2^{2-1}(2{-}1)\,5^{1-1}(5{-}1)=2\cdot 1\cdot 1\cdot 4=8.}

Fourier transform

[edit]

The totient is thediscrete Fourier transform of thegcd, evaluated at 1.[17] Let

F{x}[m]=∑k=1nxk⋅e−2πimkn{\displaystyle {\mathcal {F}}\{\mathbf {x} \}[m]=\sum \limits _{k=1}^{n}x_{k}\cdot e^{{-2\pi i}{\frac {mk}{n}}}}

wherexk = gcd(k,n) fork ∈ {1, ...,n}. Then

φ(n)=F{x}[1]=∑k=1ngcd(k,n)e−2πikn.{\displaystyle \varphi (n)={\mathcal {F}}\{\mathbf {x} \}[1]=\sum \limits _{k=1}^{n}\gcd(k,n)e^{-2\pi i{\frac {k}{n}}}.}

The real part of this formula is

φ(n)=∑k=1ngcd(k,n)cos⁡2πkn.{\displaystyle \varphi (n)=\sum \limits _{k=1}^{n}\gcd(k,n)\cos {\tfrac {2\pi k}{n}}.}

For example, usingcos⁡π5=5+14{\displaystyle \cos {\tfrac {\pi }{5}}={\tfrac {{\sqrt {5}}+1}{4}}} andcos⁡2π5=5−14{\displaystyle \cos {\tfrac {2\pi }{5}}={\tfrac {{\sqrt {5}}-1}{4}}}:φ(10)=gcd(1,10)cos⁡2π10+gcd(2,10)cos⁡4π10+gcd(3,10)cos⁡6π10+⋯+gcd(10,10)cos⁡20π10=1⋅(5+14)+2⋅(5−14)+1⋅(−5−14)+2⋅(−5+14)+5⋅(−1)+ 2⋅(−5+14)+1⋅(−5−14)+2⋅(5−14)+1⋅(5+14)+10⋅(1)=4.{\displaystyle {\begin{array}{rcl}\varphi (10)&=&\gcd(1,10)\cos {\tfrac {2\pi }{10}}+\gcd(2,10)\cos {\tfrac {4\pi }{10}}+\gcd(3,10)\cos {\tfrac {6\pi }{10}}+\cdots +\gcd(10,10)\cos {\tfrac {20\pi }{10}}\\&=&1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+5\cdot (-1)\\&&+\ 2\cdot (-{\tfrac {{\sqrt {5}}+1}{4}})+1\cdot (-{\tfrac {{\sqrt {5}}-1}{4}})+2\cdot ({\tfrac {{\sqrt {5}}-1}{4}})+1\cdot ({\tfrac {{\sqrt {5}}+1}{4}})+10\cdot (1)\\&=&4.\end{array}}}Unlike theEuler product and the divisor sum formula, this one does not require knowing the factors ofn. However, it does involve the calculation of the greatest common divisor ofn and every positive integer less thann, which suffices to provide the factorization anyway.

Divisor sum

[edit]

The property established by Gauss,[18] that

∑d∣nφ(d)=n,{\displaystyle \sum _{d\mid n}\varphi (d)=n,}

where the sum is over all positive divisorsd ofn, can be proven in several ways. (SeeArithmetical function for notational conventions.)

One proof is to note thatφ(d) is also equal to the number of possible generators of thecyclic groupCd ; specifically, ifCd = ⟨g⟩ withgd = 1, thengk is a generator for everyk coprime tod. Since every element ofCn generates a cyclicsubgroup, and each subgroupCd ⊆Cn is generated by preciselyφ(d) elements ofCn, the formula follows.[19] Equivalently, the formula can be derived by the same argument applied to themultiplicative group of thenth roots of unity and theprimitivedth roots of unity.

The formula can also be derived from elementary arithmetic.[20] For example, letn = 20 and consider the positive fractions up to 1 with denominator 20:

120,220,320,420,520,620,720,820,920,1020,1120,1220,1320,1420,1520,1620,1720,1820,1920,2020.{\displaystyle {\tfrac {1}{20}},\,{\tfrac {2}{20}},\,{\tfrac {3}{20}},\,{\tfrac {4}{20}},\,{\tfrac {5}{20}},\,{\tfrac {6}{20}},\,{\tfrac {7}{20}},\,{\tfrac {8}{20}},\,{\tfrac {9}{20}},\,{\tfrac {10}{20}},\,{\tfrac {11}{20}},\,{\tfrac {12}{20}},\,{\tfrac {13}{20}},\,{\tfrac {14}{20}},\,{\tfrac {15}{20}},\,{\tfrac {16}{20}},\,{\tfrac {17}{20}},\,{\tfrac {18}{20}},\,{\tfrac {19}{20}},\,{\tfrac {20}{20}}.}

Put them into lowest terms:

120,110,320,15,14,310,720,25,920,12,1120,35,1320,710,34,45,1720,910,1920,11{\displaystyle {\tfrac {1}{20}},\,{\tfrac {1}{10}},\,{\tfrac {3}{20}},\,{\tfrac {1}{5}},\,{\tfrac {1}{4}},\,{\tfrac {3}{10}},\,{\tfrac {7}{20}},\,{\tfrac {2}{5}},\,{\tfrac {9}{20}},\,{\tfrac {1}{2}},\,{\tfrac {11}{20}},\,{\tfrac {3}{5}},\,{\tfrac {13}{20}},\,{\tfrac {7}{10}},\,{\tfrac {3}{4}},\,{\tfrac {4}{5}},\,{\tfrac {17}{20}},\,{\tfrac {9}{10}},\,{\tfrac {19}{20}},\,{\tfrac {1}{1}}}

These twenty fractions are all the positive⁠k/d⁠ ≤ 1 whose denominators are the divisorsd = 1, 2, 4, 5, 10, 20. The fractions with 20 as denominator are those with numerators relatively prime to 20, namely⁠1/20⁠,⁠3/20⁠,⁠7/20⁠,⁠9/20⁠,⁠11/20⁠,⁠13/20⁠,⁠17/20⁠,⁠19/20⁠; by definition this isφ(20) fractions. Similarly, there areφ(10) fractions with denominator 10, andφ(5) fractions with denominator 5, etc. Thus the set of twenty fractions is split into subsets of sizeφ(d) for eachd dividing 20. A similar argument applies for anyn.

Möbius inversion applied to the divisor sum formula gives

φ(n)=∑d∣nμ(d)⋅nd=n∑d∣nμ(d)d,{\displaystyle \varphi (n)=\sum _{d\mid n}\mu \left(d\right)\cdot {\frac {n}{d}}=n\sum _{d\mid n}{\frac {\mu (d)}{d}},}

whereμ is theMöbius function, themultiplicative function defined byμ(p)=−1{\displaystyle \mu (p)=-1} andμ(pk)=0{\displaystyle \mu (p^{k})=0} for each primep andk ≥ 2. This formula may also be derived from the product formula by multiplying out∏p∣n(1−1p){\textstyle \prod _{p\mid n}(1-{\frac {1}{p}})} to get∑d∣nμ(d)d.{\textstyle \sum _{d\mid n}{\frac {\mu (d)}{d}}.}

An example:φ(20)=μ(1)⋅20+μ(2)⋅10+μ(4)⋅5+μ(5)⋅4+μ(10)⋅2+μ(20)⋅1=1⋅20−1⋅10+0⋅5−1⋅4+1⋅2+0⋅1=8.{\displaystyle {\begin{aligned}\varphi (20)&=\mu (1)\cdot 20+\mu (2)\cdot 10+\mu (4)\cdot 5+\mu (5)\cdot 4+\mu (10)\cdot 2+\mu (20)\cdot 1\\[.5em]&=1\cdot 20-1\cdot 10+0\cdot 5-1\cdot 4+1\cdot 2+0\cdot 1=8.\end{aligned}}}

Some values

[edit]

The first 100 values (sequenceA000010 in theOEIS) are shown in the table and graph below:

Graph of the first 100 values
φ(n) for1 ≤n ≤ 100
+12345678910
01122426464
1010412688166188
20121022820121812288
3030162016241236182416
4040124220242246164220
5032245218402436285816
6060303632482066324424
7070247236403660247832
8054408224644256408824
9072446046723296426040

In the graph at right the top liney =n − 1 is anupper bound valid for alln other than one, and attained if and only ifn is a prime number. A simple lower bound isφ(n)≥n/2{\displaystyle \varphi (n)\geq {\sqrt {n/2}}}, which is rather loose: in fact, thelower limit of the graph is proportional to⁠n/log logn⁠.[21]

Euler's theorem

[edit]
Main article:Euler's theorem

This states that ifa andn arerelatively prime then

aφ(n)≡1modn.{\displaystyle a^{\varphi (n)}\equiv 1\mod n.}

The special case wheren is prime is known asFermat's little theorem.

This follows fromLagrange's theorem and the fact thatφ(n) is theorder of themultiplicative group of integers modulon.

TheRSA cryptosystem is based on this theorem: it implies that theinverse of the functiona ↦ae modn, wheree is the (public) encryption exponent, is the functionb ↦bd modn, whered, the (private) decryption exponent, is themultiplicative inverse ofe moduloφ(n). The difficulty of computingφ(n) without knowing the factorization ofn is thus the difficulty of computingd: this is known as theRSA problem which can be solved by factoringn. The owner of the private key knows the factorization, since an RSA private key is constructed by choosingn as the product of two (randomly chosen) large primesp andq. Onlyn is publicly disclosed, and given thedifficulty to factor large numbers we have the guarantee that no one else knows the factorization.

Other formulae

[edit]
Compare this to the formulalcm⁡(m,n)⋅gcd⁡(m,n)=m⋅n{\textstyle \operatorname {lcm} (m,n)\cdot \operatorname {gcd} (m,n)=m\cdot n} (seeleast common multiple).
whererad(n) is theradical ofn (the product of all distinct primes dividingn).

Menon's identity

[edit]
Main article:Menon's identity

In 1965 P. Kesava Menon proved

∑gcd(k,n)=11≤k≤ngcd(k−1,n)=φ(n)d(n),{\displaystyle \sum _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\!\!\!\!\gcd(k-1,n)=\varphi (n)d(n),}

whered(n) =σ0(n) is the number of divisors ofn.

Divisibility by any fixed positive integer

[edit]

The following property, which is unpublished as a specific result but has long been known,[26] has important consequences. For instance it rules out uniform distribution of the values ofφ(n){\displaystyle \varphi (n)} in the arithmetic progressions moduloq{\displaystyle q} for any integerq>1{\displaystyle q>1}.

This is an elementary consequence of the fact that the sum of the reciprocals of the primes congruent to 1 moduloq{\displaystyle q} diverges, which itself is a corollary of the proof ofDirichlet's theorem on arithmetic progressions.

Generating functions

[edit]

TheDirichlet series forφ(n) may be written in terms of theRiemann zeta function as:[27]

∑n=1∞φ(n)ns=ζ(s−1)ζ(s){\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)}{n^{s}}}={\frac {\zeta (s-1)}{\zeta (s)}}}

where the left-hand side converges forℜ(s)>2{\displaystyle \Re (s)>2}.

TheLambert series generating function is[28]

∑n=1∞φ(n)qn1−qn=q(1−q)2{\displaystyle \sum _{n=1}^{\infty }{\frac {\varphi (n)q^{n}}{1-q^{n}}}={\frac {q}{(1-q)^{2}}}}

which converges for|q| < 1.

Both of these are proved by elementary series manipulations and the formulae forφ(n).

Growth rate

[edit]

In the words of Hardy & Wright, the order ofφ(n) is "always 'nearlyn'."[29]

First[30]

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

but asn goes to infinity,[31] for allδ > 0

φ(n)n1−δ→∞.{\displaystyle {\frac {\varphi (n)}{n^{1-\delta }}}\rightarrow \infty .}

These two formulae can be proved by using little more than the formulae forφ(n) and thedivisor sum functionσ(n).

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

6π2<φ(n)σ(n)n2<1,{\displaystyle {\frac {6}{\pi ^{2}}}<{\frac {\varphi (n)\sigma (n)}{n^{2}}}<1,}

true forn > 1, is proved.

We also have[21]

liminfφ(n)nlog⁡log⁡n=e−γ.{\displaystyle \lim \inf {\frac {\varphi (n)}{n}}\log \log n=e^{-\gamma }.}

Hereγ isEuler's constant,γ = 0.577215665..., soeγ = 1.7810724... ande−γ = 0.56145948....

Proving this does not quite require theprime number theorem.[32][33] Sincelog logn goes to infinity, this formula shows that

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

In fact, more is true.[34][35][36]

φ(n)>neγlog⁡log⁡n+3log⁡log⁡nfor n>2{\displaystyle \varphi (n)>{\frac {n}{e^{\gamma }\;\log \log n+{\frac {3}{\log \log n}}}}\quad {\text{for }}n>2}

and

φ(n)<neγlog⁡log⁡nfor infinitely many n.{\displaystyle \varphi (n)<{\frac {n}{e^{\gamma }\log \log n}}\quad {\text{for infinitely many }}n.}

The second inequality was shown byJean-Louis Nicolas.Ribenboim says "The method of proof is interesting, in that the inequality is shown first under the assumption that theRiemann hypothesis is true, secondly under the contrary assumption."[36]: 173 

For the average order, we have[23][37]

φ(1)+φ(2)+⋯+φ(n)=3n2π2+O(n(log⁡n)23(log⁡log⁡n)43)as n→∞,{\displaystyle \varphi (1)+\varphi (2)+\cdots +\varphi (n)={\frac {3n^{2}}{\pi ^{2}}}+O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {4}{3}}\right)\quad {\text{as }}n\rightarrow \infty ,}

due toArnold Walfisz, its proof exploiting estimates on exponential sums due toI. M. Vinogradov andN. 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

O(n(log⁡n)23(log⁡log⁡n)13){\displaystyle O\left(n(\log n)^{\frac {2}{3}}(\log \log n)^{\frac {1}{3}}\right)}

(this is currently the best known estimate of this type). The"BigO" stands for a quantity that is bounded by a constant times the function ofn inside the parentheses (which is small compared ton2).

This result can be used to prove[38] thatthe probability of two randomly chosen numbers being relatively prime is⁠6/π2⁠.

Ratio of consecutive values

[edit]

In 1950 Somayajulu proved[39][40]

liminfφ(n+1)φ(n)=0andlimsupφ(n+1)φ(n)=∞.{\displaystyle {\begin{aligned}\lim \inf {\frac {\varphi (n+1)}{\varphi (n)}}&=0\quad {\text{and}}\\[5px]\lim \sup {\frac {\varphi (n+1)}{\varphi (n)}}&=\infty .\end{aligned}}}

In 1954Schinzel andSierpiński strengthened this, proving[39][40] that the set

{φ(n+1)φ(n),n=1,2,…}{\displaystyle \left\{{\frac {\varphi (n+1)}{\varphi (n)}},\;\;n=1,2,\ldots \right\}}

isdense in the positive real numbers. They also proved[39] that the set

{φ(n)n,n=1,2,…}{\displaystyle \left\{{\frac {\varphi (n)}{n}},\;\;n=1,2,\ldots \right\}}

is dense in the interval (0,1).

Totient number

[edit]

Atotient number is a value of Euler's totient function: that is, anm for which there is at least onen for whichφ(n) =m. Thevalency ormultiplicity of a totient numberm is the number of solutions to this equation.[41] Anontotient 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,[42] and indeed every positive integer has a multiple which is an even nontotient.[43]

The first few totient numbers are1,2,4,6,8,10,12,16,18,20{\displaystyle 1,2,4,6,8,10,12,16,18,20}, see sequenceA002202.

The number of totient numbers up to a given limitx is

xlog⁡xe(C+o(1))(log⁡log⁡log⁡x)2{\displaystyle {\frac {x}{\log x}}e^{{\big (}C+o(1){\big )}(\log \log \log x)^{2}}}

for a constantC = 0.8178146....[44]

If counted accordingly to multiplicity, the number of totient numbers up to a given limitx is

|{n:φ(n)≤x}|=ζ(2)ζ(3)ζ(6)⋅x+R(x){\displaystyle {\Big \vert }\{n:\varphi (n)\leq x\}{\Big \vert }={\frac {\zeta (2)\zeta (3)}{\zeta (6)}}\cdot x+R(x)}

where the error termR is of order at most⁠x/(logx)k⁠ for any positivek.[45]

It is known that the multiplicity ofm exceedsmδ infinitely often for anyδ < 0.55655.[46][47]

Ford's theorem

[edit]

Ford (1999) proved that for every integerk ≥ 2 there is a totient numberm of multiplicityk: that is, for which the equationφ(n) =m has exactlyk solutions; this result had previously been conjectured byWacław Sierpiński,[48] and it had been obtained as a consequence ofSchinzel's hypothesis H.[44] Indeed, each multiplicity that occurs, does so infinitely often.[44][47]

However, no numberm is known with multiplicityk = 1.Carmichael's totient function conjecture is the statement that there is no suchm.[49]

Perfect totient numbers

[edit]
Main article:Perfect totient number

A perfect totient number is an integer that is equal to the sum of its iterated totients. That is, we apply the totient function to a numbern, apply it again to the resulting totient, and so on, until the number 1 is reached, and add together the resulting sequence of numbers; if the sum equalsn, thenn is a perfect totient number.

Applications

[edit]

Cyclotomy

[edit]
Main article:Constructible polygon

In the last section of theDisquisitiones[50][51] Gauss proves[52] that a regularn-gon can be constructed with straightedge and compass ifφ(n) is a power of 2. Ifn is a power of an odd prime number the formula for the totient says its totient can be a power of two only ifn is a first power andn − 1 is a power of 2. The primes that are one more than a power of 2 are calledFermat primes, and only five are known: 3, 5, 17, 257, and 65537. Fermat and Gauss knew of these. Nobody has been able to prove whether there are any more.

Thus, a regularn-gon has a straightedge-and-compass construction ifn is a product of distinct Fermat primes and any power of 2. The first few suchn are[53]

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40,... (sequenceA003401 in theOEIS).

Prime number theorem for arithmetic progressions

[edit]
Main article:Prime number theorem § Prime number theorem for arithmetic progressions

The RSA cryptosystem

[edit]
Main article:RSA cryptosystem

Setting up an RSA system involves choosing large prime numbersp andq, computingn =pq andk =φ(n), and finding two numberse andd such thated ≡ 1 (modk). The numbersn ande (the "encryption key") are released to the public, andd (the "decryption key") is kept private.

A message, represented by an integerm, where0 <m <n, is encrypted by computingS =me (modn).

It is decrypted by computingt =Sd (modn). Euler's Theorem can be used to show that if0 <t <n, thent =m.

The security of an RSA system would be compromised if the numbern could be efficiently factored or ifφ(n) could be efficiently computed without factoringn.

Unsolved problems

[edit]

Lehmer's conjecture

[edit]
Main article:Lehmer's totient problem

Ifp is prime, thenφ(p) =p − 1. In 1932D. H. Lehmer asked if there are any composite numbersn such thatφ(n) dividesn − 1. None are known.[54]

In 1933 he proved that if any suchn exists, it must be odd, square-free, and divisible by at least seven primes (i.e.ω(n) ≥ 7). In 1980 Cohen and Hagis proved thatn > 1020 and thatω(n) ≥ 14.[55] Further, Hagis showed that if 3 dividesn thenn > 101937042 andω(n) ≥ 298848.[56][57]

Carmichael's conjecture

[edit]
Main article:Carmichael's totient function conjecture

This states that there is no numbern{\displaystyle n} with the property that for all other numbersm{\displaystyle m},m≠n{\displaystyle m\neq n},φ(m)≠φ(n){\displaystyle \varphi (m)\neq \varphi (n)}. SeeFord's theorem above.

If there is a single counterexample to this conjecture, there must be infinitely many counterexamples, and the smallest one has at least ten billion digits in base 10.[41]

Riemann hypothesis

[edit]

TheRiemann hypothesis is trueif and only if the inequality

nφ(n)<eγlog⁡log⁡n+eγ(4+γ−log⁡4π)log⁡n{\displaystyle {\frac {n}{\varphi (n)}}<e^{\gamma }\log \log n+{\frac {e^{\gamma }(4+\gamma -\log 4\pi )}{\sqrt {\log n}}}}

is true for alln≥p120569#{\displaystyle n\geq p_{120569}\#} whereγ{\displaystyle \gamma } isEuler's constant andp120569#{\displaystyle p_{120569}\#} is theproduct of the first120569 primes.[58]

See also

[edit]

Notes

[edit]
  1. ^"Euler's totient function".Khan Academy. Retrieved2016-02-26.
  2. ^Long (1972, p. 85)
  3. ^Pettofrezzo & Byrkit (1970, p. 72)
  4. ^Long (1972, p. 162)
  5. ^Pettofrezzo & Byrkit (1970, p. 80)
  6. ^SeeEuler's theorem.
  7. ^L. Euler "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,ed.,Leonhardi Euleri Commentationes Arithmeticae, volume 1, in:Leonhardi Euleri Opera Omnia, series 1, volume 2 (Leipzig, Germany, B. G. Teubner, 1915),pages 531–555. On page 531, Euler definesn{\displaystyle n} as the number of integers that are smaller thanN{\displaystyle N} and relatively prime toN{\displaystyle N} (... aequalis sit multitudini numerorum ipso N minorum, qui simul ad eum sint primi, ...), which is the phi function, φ(N).
  8. ^abSandifer, p. 203
  9. ^Graham et al. p. 133 note 111
  10. ^L. Euler,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).
  11. ^Bothφ(n) andϕ(n) are seen in the literature. These are two forms of the lower-case Greek letterphi.
  12. ^Gauss,Disquisitiones Arithmeticae article 38
  13. ^Cajori, Florian (1929).A History Of Mathematical Notations Volume II. Open Court Publishing Company. §409.
  14. ^J. J. Sylvester (1879) "On certain ternary cubic-form equations",American Journal of Mathematics,2 : 357-393; Sylvester coins the term "totient" onpage 361.
  15. ^"totient".Oxford English Dictionary (2nd ed.).Oxford University Press. 1989.
  16. ^Weisstein, Eric W."Totient Function".mathworld.wolfram.com. Retrieved2025-02-09.
  17. ^Schramm (2008)
  18. ^Gauss, DA, art 39
  19. ^Gauss, DA art. 39, arts. 52-54
  20. ^Graham et al. pp. 134-135
  21. ^abHardy & Wright 1979, thm. 328
  22. ^Dineva (in external refs), prop. 1
  23. ^abcWalfisz, Arnold (1963).Weylsche Exponentialsummen in der neueren Zahlentheorie. Mathematische Forschungsberichte (in German). Vol. 16. Berlin:VEB Deutscher Verlag der Wissenschaften.Zbl 0146.06003.
  24. ^Lomadse, G. (1964),"The scientific work of Arnold Walfisz"(PDF),Acta Arithmetica,10 (3):227–237,doi:10.4064/aa-10-3-227-237
  25. ^abSitaramachandrarao, R. (1985)."On an error term of Landau II".Rocky Mountain J. Math.15 (2):579–588.doi:10.1216/RMJ-1985-15-2-579.
  26. ^Pollack, P. (2023), "Two problems on the distribution of Carmichael's lambda function",Mathematika,69 (4):1195–1220,arXiv:2303.14043,doi:10.1112/mtk.12222
  27. ^Hardy & Wright 1979, thm. 288
  28. ^Hardy & Wright 1979, thm. 309
  29. ^Hardy & Wright 1979, intro to § 18.4
  30. ^Hardy & Wright 1979, thm. 326
  31. ^Hardy & Wright 1979, thm. 327
  32. ^In fact Chebyshev's theorem (Hardy & Wright 1979, thm.7) andMertens' third theorem is all that is needed.
  33. ^Hardy & Wright 1979, thm. 436
  34. ^Theorem 15 ofRosser, J. Barkley; Schoenfeld, Lowell (1962)."Approximate formulas for some functions of prime numbers".Illinois J. Math.6 (1):64–94.doi:10.1215/ijm/1255631807.
  35. ^Bach & Shallit, thm. 8.8.7
  36. ^abRibenboim (1989). "How are the Prime Numbers Distributed? §I.C The Distribution of Values of Euler's Function".The Book of Prime Number Records (2nd ed.). New York: Springer-Verlag. pp. 172–175.doi:10.1007/978-1-4684-0507-1_5.ISBN 978-1-4684-0509-5.
  37. ^Sándor, Mitrinović & Crstici (2006) pp.24–25
  38. ^Hardy & Wright 1979, thm. 332
  39. ^abcRibenboim, p.38
  40. ^abSándor, Mitrinović & Crstici (2006) p.16
  41. ^abGuy (2004) p.144
  42. ^Sándor & Crstici (2004) p.230
  43. ^Zhang, Mingzhi (1993)."On nontotients".Journal of Number Theory.43 (2):168–172.doi:10.1006/jnth.1993.1014.ISSN 0022-314X.Zbl 0772.11001.
  44. ^abcFord, Kevin (1998). "The distribution of totients".Ramanujan J.2 (1–2):67–151.doi:10.1023/A:1009761909132.ISSN 1382-4090.Zbl 0914.11053. Reprinted in Analytic and Elementary Number Theory: A Tribute to Mathematical Legend Paul Erdos, Developments in Mathematics, vol. 1, 1998,doi:10.1007/978-1-4757-4507-8_8,ISBN 978-1-4419-5058-1. Updated and corrected inarXiv:1104.3264, 2011.
  45. ^Sándor et al (2006) p.22
  46. ^Sándor et al (2006) p.21
  47. ^abGuy (2004) p.145
  48. ^Sándor & Crstici (2004) p.229
  49. ^Sándor & Crstici (2004) p.228
  50. ^Gauss, DA. The 7th § is arts. 336–366
  51. ^Gauss proved ifn satisfies certain conditions then then-gon can be constructed. In 1837Pierre Wantzel proved the converse, if then-gon is constructible, thenn must satisfy Gauss's conditions
  52. ^Gauss, DA, art 366
  53. ^Gauss, DA, art. 366. This list is the last sentence in theDisquisitiones
  54. ^Ribenboim, pp. 36–37.
  55. ^Cohen, Graeme L.; Hagis, Peter Jr. (1980). "On the number of prime factors ofn ifφ(n) dividesn − 1".Nieuw Arch. Wiskd. III Series.28:177–185.ISSN 0028-9825.Zbl 0436.10002.
  56. ^Hagis, Peter Jr. (1988). "On the equationM·φ(n) =n − 1".Nieuw Arch. Wiskd. IV Series.6 (3):255–261.ISSN 0028-9825.Zbl 0668.10006.
  57. ^Guy (2004) p.142
  58. ^Broughan, Kevin (2017).Equivalents of the Riemann Hypothesis, Volume One: Arithmetic Equivalents (First ed.). Cambridge University Press.ISBN 978-1-107-19704-6. Corollary 5.35

References

[edit]

TheDisquisitiones Arithmeticae has been translated from Latin into English and German. The German edition includes all of Gauss's papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

References to theDisquisitiones are of the form Gauss, DA, art.nnn.

External links

[edit]
Totient function
Retrieved from "https://en.wikipedia.org/w/index.php?title=Euler%27s_totient_function&oldid=1336934126"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp