Euler indikátor

Az itt bemutatott két generáló függvényt a fenti φ = μ ✻ Id és φ ✻ 1 = Id képlet segítségével számoljuk ki .

Mivel a Dirichlet sor generáló μ jelentése 1 / ζ ( s ) -, ahol ζ a Riemann zéta-függvény -, és hogy a Id jelentése ζ ( s - 1) , vezetjük le , hogy a φ (amely konvergál az Re ( s )> 2 ) :

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

A φ-hez társított Lambert-sorozat (amely konvergál a | q | <1-re) az

∑nem=1∞φ(nem)qnem1-qnem=∑m=1∞mqm=q(1-q)2.{\ displaystyle \ sum _ {n = 1} ^ {\ infty} {\ frac {\ varphi (n) q ^ {n}} {1-q ^ {n}}} = \ sum _ {m = 1} ^ {\ infty} mq ^ {m} = {\ frac {q} {(1-q) ^ {2}}}.}

Arnold Walfisz létrehozta

∑nem≤xφ(nem)=3π2x2+O(x(napló⁡x)2/3(napló⁡napló⁡x)4/3)  (x→∞){\ displaystyle \ sum _ {n \ leq x} \ varphi (n) = {\ frac {3} {\ pi ^ {2}}} x ^ {2} + O \ bal (x (\ log x) ^ {2/3} (\ log \ log x) ^ {4/3} \ right) \ \ (x \ rightarrow \ infty)}

(ahol O a nagy O Landau ), kihasználva, többek között becslések exponenciális összegek miatt IM Vinogradov és NM Korobov . A mai napig ez még mindig a legjobb becslése a típusában.

Funkciónövekedés

Aszimptotikusan van

nem1-ϵ<φ(nem)≤nem-1 {\ displaystyle n ^ {1- \ epsilon} <\ varphi (n) \ leq n-1 \}

bármelyiknek és . A felső határ egyenlősége akkor teljesül, ha n prímszám. És ha figyelembe vesszük a kapcsolatot ϵ>0{\ displaystyle \ epsilon> 0 \,}nem>NEM(ϵ){\ displaystyle n> N (\ epsilon) \,}

φ(nem)nem=∏o|nem, o első(1-o-1){\ displaystyle {\ frac {\ varphi (n)} {n}} = \ prod _ {p | n, \ p {\ text {first}}} (1-p ^ {- 1}) \,}

láthatjuk, hogy az értékek az N megfelelő a különösen a kis értékek az a primorial n , vagyis azokat, amelyek a terméket a kezdeti szegmense a szekvencia az összes prímszám. Tól Mertens' harmadik tétel és Csebisev egyenlőtlenség tudjuk mutatni, hogy a fenti becslés lehet helyettesíteni φ(nem)nem{\ displaystyle {\ frac {\ varphi (n)} {n}}}

e-γnemln⁡ln⁡nem(1+o(1))<φ(nem)≤nem-1 {\ displaystyle {\ frac {{\ rm {e}} ^ {- \ gamma} n} {\ ln \ ln n}} (1 + o (1)) <\ varphi (n) \ leq n-1 \ }

(ahol o jelentése a kis o Landau és a Euler-Mascheroni állandó ), és hogy a csökkentés optimális. γ{\ displaystyle \ gamma}

Más formulák, amelyek Euler φ funkcióját tartalmazzák

• ∀nál nél>0,∀nem>1nem|φ(nál nélnem-1){\ displaystyle \ forall a> 0, \ forall n> 1 \ quad n | \ varphi (a ^ {n} -1)}
  mert a multiplikatív sorrendben az egy modulo egy n - 1 jelentése n .
• φ(mnem)=φ(m)φ(nem)dφ(d) mert d=ogvs.d(m,nem),{\ displaystyle \ varphi (mn) = \ varphi (m) \ varphi (n) {\ frac {d} {\ varphi (d)}} {\ text {for}} d = {\ rm {pgcd}} ( m, n),}
  különösen :
  • φ(2m)={2φ(m) ha m egyenlőφ(m) ha m furcsa{\ displaystyle \ varphi (2m) = {\ begin {cases} 2 \ varphi (m) & {\ text {si}} m {\ text {is}} \\\ varphi (m) & {\ text { ha}} m {\ text {páratlan}} \ vég {esetek}}}
  • ∀k≥1φ(nemk)=nemk-1φ(nem).{\ displaystyle \ összes k \ geq 1 \ quad \ varphi (n ^ {k}) = n ^ {k-1} \ varphi (n).}
• ∑d∣nemμ2(d)φ(d)=nemφ(nem).{\ displaystyle \ sum _ {d \ mid n} {\ frac {\ mu ^ {2} (d)} {\ varphi (d)}} = {\ frac {n} {\ varphi (n)}}. }
• ∀nem>1∑1≤k≤nemogvs.d(k,nem)=1k=12nemφ(nem).{\ displaystyle \ forall n> 1 \ quad \ sum _ {1 \ leq k \ leq n \ tetején {\ rm {pgcd}} (k, n) = 1} k = {\ frac {1} {2}} n \ varphi (n).}
• ∑k=1nemφ(k)=12(1+∑k=1nemμ(k)⌊nemk⌋2).{\ displaystyle \ sum _ {k = 1} ^ {n} \ varphi (k) = {\ frac {1} {2}} \ bal (1+ \ sum _ {k = 1} ^ {n} \ mu (k) \ bal \ lfloor {\ frac {n} {k}} \ right \ rfloor ^ {2} \ right).}
• 1965-ben P. Kesava Menon demonstrált∑ogvs.d1≤k≤nem(k,nem)=1ogvs.d(k-1,nem)=φ(nem)d(nem){\ displaystyle \ sum _ {{\ stackrel {1 \ leq k \ leq n} {\ rm {pgcd}}} (k, n) = 1} {\ rm {pgcd}} (k-1, n) = \ varphi (n) d (n)}ahol d a funkció száma osztója

B. Sury∑ogvs.d(k1,nem)=11≤k1,k2,...,ks≤nemogvs.d(k1-1,k2,...,ks,nem)=φ(nem)σs-1(nem){\ displaystyle \ sum _ {\ stackrel {1 \ leq k_ {1}, k_ {2}, \ dots, k_ {s} \ leq n} {{\ rm {pgcd}} (k_ {1}, n) = 1}} {\ rm {pgcd}} (k_ {1} -1, k_ {2}, \ pontok, k_ {s}, n) = \ varphi (n) \ sigma _ {s-1} (n )} ahol σ egy az összeg függvényében a hatáskörét a -ths az osztó .

N. Rao∑ogvs.d(k1,k2,...,ks,nem)=11≤k1,k2,...,ks≤nemogvs.d(k1-nál nél1,k2-nál nél2,...,ks-nál néls,nem)s=Js(nem)d(nem){\ displaystyle \ sum _ {\ stackrel {1 \ leq k_ {1}, k_ {2}, \ dots, k_ {s} \ leq n} {{\ rm {pgcd}} (k_ {1}, k_ { 2}, \ pontok, k_ {s}, n) = 1}} {\ rm {pgcd}} (k_ {1} -a_ {1}, k_ {2} -a_ {2}, \ pontok, k_ { s} -a_ {s}, n) ^ {s} = J_ {s} (n) d (n)} ahol egy 1 , egy 2 , ..., a s jelentése egész szám, hogy lnko ( a 1 , a 2 , ..., egy s , n ) = 1 és J s jelentése Jordan Totient funkciót .

L. Tóth∑ogvs.d(k,m)=11≤k≤mogvs.d(k2-1,m1)gcd(k2-1,m2)=φ(nem)∑d2∣m2d1∣m1φ(ogvs.d(d1,d2))2ω(oovs.m(d1,d2)){\ displaystyle \ sum _ {\ stackrel {1 \ leq k \ leq m} {{\ rm {pgcd}} (k, m) = 1}} {\ rm {pgcd}} (k ^ {2} -1 , m_ {1}) \ gcd (k ^ {2} -1, m_ {2}) = \ varphi (n) \ sum _ {\ stackrel {d_ {1} \ m m {1}} {d_ {2 } \ mid m_ {2}}} \ varphi ({\ rm {pgcd}} (d_ {1}, d_ {2})) 2 ^ {\ omega ({\ rm {ppcm}} (d_ {1}, d_ {2}))}} ahol m 1 és m 2 páratlan, m = ppcm ( m 1 , m 2 ) és ω a különálló osztók függvényszáma .

Valójában bármely f aritmetikai függvény esetében ∑ogvs.d(k,nem)=11≤k≤nemf(ogvs.d(k-1,nem))=φ(nem)∑d∣nem(μ∗f)(d)φ(d).{\ displaystyle \ sum _ {\ stackrel {1 \ leq k \ leq n} {{\ rm {pgcd}} (k, n) = 1}} f ({\ rm {pgcd}} (k-1, n )) = \ varphi (n) \ sum _ {d \ mid n} {\ frac {(\ mu * f) (d)} {\ varphi (d)}}}

• ∑k=1nemφ(k)k=∑k=1nemμ(k)k⌊nemk⌋=6.π2nem+O((napló⁡nem)2/3(napló⁡napló⁡nem)4/3){\ displaystyle \ sum _ {k = 1} ^ {n} {\ frac {\ varphi (k)} {k}} = \ sum _ {k = 1} ^ {n} {\ frac {\ mu (k )} {k}} \ left \ lfloor {\ frac {n} {k}} \ right \ rfloor = {\ frac {6} {\ pi ^ {2}}} n + O \ left ((\ log n ) ^ {2/3} (\ log \ log n) ^ {4/3} \ right)} .
• ∑k=1nemkφ(k)=315 ζ(3)2π4nem-napló⁡nem2+O((napló⁡nem)2/3){\ displaystyle \ sum _ {k = 1} ^ {n} {\ frac {k} {\ varphi (k)}} = {\ frac {315 ~ \ zeta (3)} {2 \ pi ^ {4} }} n - {\ frac {\ log n} {2}} + O \ bal ((\ log n) ^ {2/3} \ jobb)} .
• ∑k=1nem1φ(k)=315 ζ(3)2π4(napló⁡nem+γ-∑o elsőnapló⁡oo2-o+1)+O((napló⁡nem)2/3nem){\ displaystyle \ sum _ {k = 1} ^ {n} {\ frac {1} {\ varphi (k)}} = {\ frac {315 ~ \ zeta (3)} {2 \ pi ^ {4} }} \ balra (\ log n + \ gamma - \ sum _ {p {\ text {first}}} {\ frac {\ log p} {p ^ {2} -p + 1}} \ jobbra) + O \ balra ({\ frac {(\ log n) ^ {2/3}} {n}} \ jobbra)} 
  ( Γ az Euler-állandó ).
• ∀m>1∑1≤k≤nemogvs.d(k,m)=11=nemφ(m)m+O(2ω(m)){\ displaystyle \ forall m> 1 \ quad \ sum _ {1 \ leq k \ leq n \ tetején {\ rm {pgcd}} (k, m) = 1} 1 = n {\ frac {\ varphi (m) } {m}} + O \ bal (2 ^ {\ omega (m)} \ jobb)}
  ahol ω ( m ) a különböző m elsődleges osztók száma .

Egyenlőtlenség

A φ funkcióval kapcsolatos egyes egyenlőtlenségek a következők:

φ(nem)>nemeγnapló⁡napló⁡nem+3napló⁡napló⁡nem{\ displaystyle \ varphi (n)> {\ frac {n} {{\ rm {e}} ^ {\ gamma} \; \ log \ log n + {\ frac {3} {\ log \ log n}} }}}

φ(nem)⩾nem2{\ displaystyle \ varphi (n) \ geqslant {\ sqrt {\ frac {n} {2}}}}

és

φ(nem)⩾nem{\ displaystyle \ varphi (n) \ geqslant {\ sqrt {n}}}

Már észrevettük, hogy n prím esetén φ ( n ) = n - 1 . Egy összetett szám n , van φ(nem)⩽nem-nem.{\ displaystyle \ varphi (n) \ leqslant n - {\ sqrt {n}}.}

Ezért minden n > 1 esetén  : 0<φ(nem)nem<1.{\ displaystyle 0 <{\ frac {\ varphi (n)} {n}} <1.}

Nagy véletlen n esetén ezek a 0 és 1 határok nem javíthatók. Valójában ezek az φ ( n ) / n alsó és felső határai .

Két egyenlőtlenség, amely egyesíti a φ függvényt és az σ osztók összegfüggvényét :

6.nem2π2<φ(nem)σ(nem)<nem2 mert nem>1.{\ displaystyle {\ frac {6n ^ {2}} {\ pi ^ {2}}} <\ varphi (n) \ sigma (n) <n ^ {2} {\ mbox {for}} n> 1. }

Sejtések

• nem{\ displaystyle n}elsődleges, ha (és csak akkor) (ez a Lehmer-probléma , Derrick Lehmer kijelentette )nem≡1modφ(nem){\ displaystyle n \ equiv 1 {\ bmod {\ varphi}} (n)}
• ∀nem>0∃m≠nemφ(nem)=φ(m){\ displaystyle \ forall {n> 0} \ quad \ létezik {m \ neq n} \ quad \ varphi (n) = \ varphi (m)}(ez az a „  Carmichael-sejtés  ”, amelyet Robert Daniel Carmichael 1907-ben kijelentett és hinni vélt, de ez továbbra is nyitott probléma ).

Megjegyzések és hivatkozások

1. L. Euler, "  Theoremata arithmetica nova methodo demonstrata  ", Novi Commentarii academiae scientiarum Petropolitanae , vol. 8, 1763, p.  74-104 , vagy Opera Omnia , 1. sorozat, vol. 2. o.  531-555 . A traktátust 1759. október 15- én mutatták be a Szentpétervári Akadémiának. 1758. június 8-án a Berlini Akadémián felolvastak egy azonos nevű szerződést.
2. L. Euler, "  Speculationes circa quasdam insignia proprietates numerorum  ", Acta Academiae Scientarum Imperialis Petropolitinae , vol. 1784, 4. o.  18-30 , vagy az Opera Omnia , 1. sorozat, vol. 4. o.  105-115 . Az értekezést 1775. október 9-én mutatták be a Szentpétervári Akadémiának.
3. Olvasson online .
4. A bemutatáshoz lásd például a "Számtani függvények" részt a "Bevezetés a számelméletbe" leckében a Wikiverzióról .
5. További részletekért lásd például a "Bevezetés a számelméletbe" leckének ezt a javított gyakorlatát a Wikiverzióról .
6. (de) A. Walfisz , Weylsche Exponentialsummen in der neueren Zahlentheorie , Berlin, VEB Deutscher Verlag der Wissenschaften ,1963.
7. (in) Tóth László, Menon azonossága és számtani összegek, amelyek több változó függvényeit képviselik , arXiv : 1103.5861v2 , eq. 1.
8. Tóth, egyenlő 5.
9. Tóth, egyenlő 3.
10. Tóth, egyenlő 35.
11. Tóth, egyenlő 2.
12. Tóth azt írja, hogy Menon 1965-ben az multiplikatív f , az V. Sita Ramaiah pedig az önkényes f esetén bizonyította .
13. (en) R. Sitaramachandrarao , „  Landau II hibatermékén  ” , Rocky Mountain J. Math. , vol.  15,1985, P.  579-588.
14. (in) Eric Bach  (in) és Jeffrey Shallit , algoritmikus számelmélet (I. kötet: hatékony algoritmusok) , MIT Press ,1996( ISBN  978-0-262-02405-1 , online olvasás ) , p.  234.
15. (in) Paulo Ribenboim , The New Book of Records prímszám , Springer ,1996, 3 e  . ( ISBN  978-0-387-94457-9 ) , p.  320.

Kapcsolódó cikkek

• Anti indikátor
• Anticindikátor
• Carmichael funkciója
• Jordan tottens függvénye
• Erősen társindikátorszám
• Nagyon jelző szám
• Gauss-Wantzel tétel
• Leonhard Eulerről elnevezett tantárgyak listája