Eulersova totientní funkce - Eulers totient function - Wikipedia

Prvních tisíc hodnot φ(n). Body na horním řádku představují φ(p) když p je prvočíslo, což je p − 1.^[1]

v teorie čísel, Eulerova totientová funkce spočítá kladná celá čísla až do daného celého čísla n to jsou relativně prime na n. Je psán řeckým dopisem phi tak jako φ(n) nebo ϕ(n), a může být také volána Eulerova phi funkce. Jinými slovy, jedná se o počet celých čísel k v dosahu 1 ≤ k ≤ n pro které největší společný dělitel gcd (n, k) se rovná 1.^[2][3] Celá čísla k této formy se někdy označují jako součty z n.

Například součty n = 9 jsou šest čísel 1, 2, 4, 5, 7 a 8. Všechna jsou relativně prvočíselná než 9, ale další tři čísla v tomto rozsahu, 3, 6 a 9 nejsou, protože gcd (9, 3) = gcd (9, 6) = 3 a gcd (9, 9) = 9. Proto, φ(9) = 6. Jako další příklad φ(1) = 1 od n = 1 jediné celé číslo v rozsahu od 1 do n je 1 samo o sobě a gcd (1, 1) = 1.

Eulerova totientová funkce je a multiplikativní funkce, což znamená, že pokud dvě čísla m a n jsou tedy relativně nejlepší φ(mn) = φ(m)φ(n).^[4][5]Tato funkce dává objednat z multiplikativní skupina celých čísel modulo n (dále jen skupina z Jednotky z prsten ℤ/nℤ).^[6] Používá se také k definování RSA šifrovací systém.

Historie, terminologie a notace

Leonhard Euler představil funkci v roce 1763.^[7][8][9] V té době si však nevybral žádný konkrétní symbol pro jeho označení. V publikaci z roku 1784 Euler studoval funkci dále a vybral si řecké písmeno π naznačit to: napsal πD pro "množství čísel menších než D, a které s ním nemají společného dělitele “.^[10] Tato definice se liší od aktuální definice funkce totient v D = 1 ale jinak je stejný. Nyní standardní notace^[8][11] φ(A) pochází z Gauss pojednání z roku 1801 Disquisitiones Arithmeticae,^[12] ačkoli Gauss kolem argumentu nepoužíval závorky a psal φA. Tak se tomu často říká Eulerova phi funkce nebo jednoduše funkce phi.

V roce 1879 J. J. Sylvester vytvořil termín totient pro tuto funkci^[13][14] takže se také označuje jako Eulerova totientová funkce, Eulerův totientnebo Eulerův totient. Jordanův totient je Eulerovo zobecnění.

The kototient z n je definován jako n − φ(n). Počítá počet kladných celých čísel menší nebo rovný n které mají alespoň jeden hlavní faktor společné s n.

Výpočet Eulerovy totientové funkce

Existuje několik vzorců pro výpočet φ(n).

Eulerův produktový vzorec

Uvádí

${ displaystyle varphi (n) = n prod _ {p mid n} left (1 - { frac {1} {p}} right),}$

kde je produkt přes odlišný prvočísla dělení n. (Pro zápis viz Aritmetická funkce.)

Ekvivalentní formulace pro ${ displaystyle n = p_ {1} ^ {k_ {1}} p_ {2} ^ {k_ {2}} cdots p_ {r} ^ {k_ {r}}}$, kde ${ displaystyle p_ {1}, p_ {2}, ldots, p_ {r}}$ jsou zřetelné rozdělení prvočísel n, je:

${ 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).}$

Důkaz těchto vzorců závisí na dvou důležitých skutečnostech.

Phi je multiplikativní funkce

To znamená, že pokud gcd (m, n) = 1, pak φ(m) φ(n) = φ(mn). Osnova důkazu: Nechat A, B, C být množiny kladných celých čísel, které jsou coprime do a méně než m, n, mn, respektive tak |A| = φ(m)atd. Pak existuje bijekce mezi A × B a C podle Čínská věta o zbytku.

Hodnota phi pro argument primární moci

Li p je hlavní a k ≥ 1, pak

${ displaystyle varphi left (p ^ {k} right) = p ^ {k} -p ^ {k-1} = p ^ {k-1} (p-1) = p ^ {k} vlevo (1 - { tfrac {1} {p}} vpravo).}$

Důkaz: Od té doby p je prvočíslo, jediné možné hodnoty gcd (p^k, m) jsou 1, p, p², ..., p^ka jediný způsob, jak mít gcd (p^k, m) > 1 je pokud m je násobkem p, tj. m = p, 2p, 3p, ..., p^{k − 1}p = p^k, a jsou p^{k − 1} takové násobky menší než p^k. Proto ten druhý p^k − p^{k − 1} čísla jsou relativně primární p^k.

Důkaz složení produktu Euler

The základní teorém aritmetiky uvádí, že pokud n > 1 existuje jedinečný výraz ${ displaystyle n = p_ {1} ^ {k_ {1}} p_ {2} ^ {k_ {2}} cdots p_ {r} ^ {k_ {r}},}$ kde p₁ < p₂ < ... < p_r jsou prvočísla a každý k_i ≥ 1. (Pouzdro n = 1 odpovídá prázdnému produktu.) Opakovaně používající multiplikativní vlastnost φ a vzorec pro φ(p^k) dává

${ 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} -1} (p_ {1} -1) , p_ {2} ^ {k_ {2} -1} (p_ {2} -1) cdots p_ {r} ^ {k_ {r} -1} (p_ {r} -1) [. 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}} vlevo (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}}}$

Získáte tak obě verze produktového vzorce Euler.

Alternativní důkaz, který nevyžaduje multiplikativní vlastnost, místo toho používá zásada začlenění-vyloučení aplikován na sadu ${ displaystyle {1,2, ldots, n }}$, s výjimkou množin celých čísel dělitelných hlavními děliteli.

Příklad

${ 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.}$

Slovy: zřetelné hlavní faktory 20 jsou 2 a 5; polovina z dvaceti celých čísel od 1 do 20 je dělitelná 2, takže deset; pětina z nich je dělitelná 5, takže osm čísel je coprime na 20; to jsou: 1, 3, 7, 9, 11, 13, 17, 19.

Alternativní vzorec používá pouze celá čísla:

${ displaystyle phi (20) = phi (2 ^ {2} 5 ^ {1}) = 2 ^ {2-1} (2 {-} 1) , 5 ^ {1-1} (5 { -} 1) = 2 cdot 1 cdot 1 cdot 4 = 8.}$

Fourierova transformace

Totient je diskrétní Fourierova transformace z gcd, hodnoceno na 1.^[15] Nechat

${ displaystyle { mathcal {F}} { mathbf {x} } [m] = součet limity _ {k = 1} ^ {n} x_ {k} cdot e ^ {{- 2 pi i} { frac {mk} {n}}}}$

kde X_k = gcd (k,n) pro k ∈ {1, …, n}. Pak

${ displaystyle varphi (n) = { mathcal {F}} { mathbf {x} } [1] = součet limity _ {k = 1} ^ {n} gcd (k, n) e ^ {- 2 pi i { frac {k} {n}}}.}$

Skutečná část tohoto vzorce je

${ displaystyle varphi (n) = součet limity _ {k = 1} ^ {n} gcd (k, n) cos { tfrac {2 pi k} {n}}.}$

Například pomocí ${ displaystyle cos { tfrac { pi} {5}} = { tfrac {{ sqrt {5}} + 1} {4}}}$ a ${ displaystyle cos { tfrac {2 pi} {5}} = { tfrac {{ sqrt {5}} - 1} {4}}}$:

${ displaystyle { begin {pole} {rcl} phi (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 {pole}}}$

Na rozdíl od Eulerova produktu a vzorce dělitele součtu tento nevyžaduje znalost faktorů n. Zahrnuje však výpočet největšího společného dělitele n a každé kladné celé číslo menší než n, což postačuje k zajištění faktorizace.

Dělitel součet

Majetek založený Gaussem,^[16] že

${ displaystyle sum _ {d mid n} varphi (d) = n,}$

kde součet převyšuje všechny kladné dělitele d z n, lze prokázat několika způsoby. (Vidět Aritmetická funkce pro notační konvence.)

Jedním z důkazů je to poznamenat φ(d) se také rovná počtu možných generátorů cyklická skupina C_d ; konkrétně pokud C_d = ⟨G⟩ s G^d = 1, pak G^k je generátor pro každého k coprime to d. Protože každý prvek C_n generuje cyklické podskupina a všechny podskupiny C_d ⊆ C_n jsou generovány nějakým prvkem C_n, následuje vzorec.^[17] Ekvivalentně lze vzorec odvodit stejným argumentem použitým na multiplikativní skupinu skupiny nth kořeny jednoty a primitivní dth kořeny jednoty.

Vzorec lze také odvodit z elementární aritmetiky.^[18] Například nechte n = 20 a zvažte kladné zlomky do 1 se jmenovatelem 20:

${ 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}}.}$

Dejme je do nejnižších podmínek:

${ 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}}}$

Těchto dvacet zlomků je pozitivních k/d ≤ 1, jehož jmenovatelem jsou dělitelé d = 1, 2, 4, 5, 10, 20. Frakce s jmenovatelem 20 jsou frakce s čitateli relativně prime k 20, jmenovitě 1/20, 3/20, 7/20, 9/20, 11/20, 13/20, 17/20, 19/20; podle definice to je φ(20) zlomky. Podobně existují φ(10) zlomky se jmenovatelem 10 a φ(5) zlomky se jmenovatelem 5 atd. Sada dvaceti zlomků je tedy rozdělena na podmnožiny velikosti φ(d) pro každého d dělení 20. Podobný argument platí pro všechny n.

Möbiova inverze aplikovaný na vzorec dělitele součtu dává

${ displaystyle varphi (n) = součet _ {d mid n} mu left (d right) cdot { frac {n} {d}} = n sum _ {d mid n} { frac { mu (d)} {d}},}$

kde μ je Möbiova funkce, multiplikativní funkce definován ${ displaystyle mu (p) = - 1}$ a ${ displaystyle mu (p ^ {k}) = 0}$ za každé prvočíslo p a k ≥ 1. Tento vzorec lze také odvodit z produktového vzorce vynásobením ${ displaystyle textstyle prod _ {p mid n} (1 - { frac {1} {p}})}}$ dostat ${ displaystyle textstyle sum _ {d mid n} { frac { mu (d)} {d}}.}$

Příklad:

${ displaystyle { begin {zarovnáno} phi (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 {zarovnáno}}}$

Některé hodnoty

Prvních 100 hodnot (sekvence A000010 v OEIS ) jsou zobrazeny v tabulce a grafu níže:

Graf prvních 100 hodnot

φ(n) pro 1 ≤ n ≤ 100

+	1	2	3	4	5	6	7	8	9	10
0	1	1	2	2	4	2	6	4	6	4
10	10	4	12	6	8	8	16	6	18	8
20	12	10	22	8	20	12	18	12	28	8
30	30	16	20	16	24	12	36	18	24	16
40	40	12	42	20	24	22	46	16	42	20
50	32	24	52	18	40	24	36	28	58	16
60	60	30	36	32	48	20	66	32	44	24
70	70	24	72	36	40	36	60	24	78	32
80	54	40	82	24	64	42	56	40	88	24
90	72	44	60	46	72	32	96	42	60	40

V grafu vpravo na horním řádku y = n − 1 je horní hranice platí pro všechny n jiný než jeden a dosažen tehdy a jen tehdy n je prvočíslo. Jednoduchá dolní mez je ${ displaystyle varphi (n) geq { sqrt {n / 2}}}$, což je dost volné: ve skutečnosti spodní limit grafu je úměrný n/log log n.^[19]

Eulerova věta

To říká, že pokud A a n jsou relativně prime pak

${ displaystyle a ^ { varphi (n)} equiv 1 mod n.}$

Zvláštní případ, kdy n je předseda je známý jako Fermatova malá věta.

To vyplývá z Lagrangeova věta a skutečnost, že φ(n) je objednat z multiplikativní skupina celých čísel modulo n.

The Kryptosystém RSA je založen na této větě: znamená to, že inverzní funkce A ↦ A^E mod n, kde E je (veřejný) šifrovací exponent, je funkce b ↦ b^d mod n, kde d, (soukromý) dešifrovací exponent, je multiplikativní inverzní z E modulo φ(n). Obtížnost výpočtu φ(n) bez znalosti faktorizace n je tedy obtížnost výpočtu d: toto je známé jako Problém RSA což lze vyřešit factoringem n. Vlastník soukromého klíče zná faktorizaci, protože soukromý klíč RSA je vytvořen výběrem n jako produkt dvou (náhodně vybraných) velkých prvočísel p a q. Pouze n je veřejně zpřístupněn a je mu uděleno obtížnost faktorovat velká čísla máme záruku, že nikdo jiný nezná faktorizaci.

Jiné vzorce

• ${ Displaystyle a mid b implikuje varphi (a) mid varphi (b)}$
• ${ displaystyle n mid varphi (a ^ {n} -1) quad { text {pro}} a, n> 1}$
• ${ displaystyle varphi (mn) = varphi (m) varphi (n) cdot { frac {d} { varphi (d)}} quad { text {kde}} d = operatorname {gcd } (m, n)}$

Všimněte si zvláštních případů

• ${ displaystyle varphi (2m) = { start {případy} 2 varphi (m) & { text {if}} m { text {je sudý}} varphi (m) & { text { if}} m { text {je zvláštní}} end {případy}}}$
• ${ displaystyle varphi left (n ^ {m} right) = n ^ {m-1} varphi (n)}$

• ${ displaystyle varphi ( operatorname {lcm} (m, n)) cdot varphi ( operatorname {gcd} (m, n)) = varphi (m) cdot varphi (n)}$

Porovnejte to se vzorcem

• ${ displaystyle operatorname {lcm} (m, n) cdot operatorname {gcd} (m, n) = m cdot n}$

(Vidět nejmenší společný násobek.)

• φ(n) je dokonce pro n ≥ 3. Navíc pokud n má r odlišné liché hlavní faktory, 2^r | φ(n)
• Pro všechny A > 1 a n > 6 takhle 4 ∤ n existuje l ≥ 2n takhle l | φ(Aⁿ − 1).
• ${ displaystyle { frac { varphi (n)} {n}} = { frac { varphi ( operatorname {rad} (n))} { operatorname {rad} (n)}}}$

kde rad (n) je radikál z n (produkt dělení všech odlišných prvočísel n ).

• ${ displaystyle sum _ {d mid n} { frac { mu ^ {2} (d)} { varphi (d)}} = { frac {n} { varphi (n)}}}$ ^[20]
• ${ displaystyle sum _ {1 leq k leq n atop (k, n) = 1} ! ! k = { tfrac {1} {2}} n varphi (n) quad { text {for}} n> 1}$
• ${ displaystyle sum _ {k = 1} ^ {n} varphi (k) = { tfrac {1} {2}} vlevo (1+ sum _ {k = 1} ^ {n} mu (k) left lfloor { frac {n} {k}} right rfloor ^ {2} right) = { frac {3} { pi ^ {2}}} n ^ {2} + O left (n ( log n) ^ { frac {2} {3}} ( log log n) ^ { frac {4} {3}} right)}$ (^[21] citováno v^[22])

• ${ 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 ) ^ { frac {2} {3}} ( log log n) ^ { frac {4} {3}} vpravo)}$ ^[21]
• ${ displaystyle sum _ {k = 1} ^ {n} { frac {k} { varphi (k)}} = { frac {315 , zeta (3)} {2 pi ^ {4 }}} n - { frac { log n} {2}} + O left (( log n) ^ { frac {2} {3}} right)}$ ^[23]
• ${ displaystyle sum _ {k = 1} ^ {n} { frac {1} { varphi (k)}} = { frac {315 , zeta (3)} {2 pi ^ {4 }}} left ( log n + gamma - sum _ {p { text {prime}}} { frac { log p} {p ^ {2} -p + 1}} right) + O left ({ frac {( log n) ^ { frac {2} {3}}} {n}} right)}$ ^[23]

(kde y je Euler – Mascheroniho konstanta ).

• ${ displaystyle sum _ { stackrel {1 leq k leq n} { operatorname {gcd} (k, m) = 1}} ! ! ! ! 1 = n { frac { varphi (m)} {m}} + O vlevo (2 ^ { omega (m)} vpravo)}$

kde m > 1 je kladné celé číslo a ω(m) je počet odlišných hlavních faktorů m.^[24]

Menonova identita

V roce 1965 se prokázal P. Kesava Menon

${ displaystyle sum _ { stackrel {1 leq k leq n} { gcd (k, n) = 1}} ! ! ! ! gcd (k-1, n) = varphi (n) d (n),}$

kde d(n) = σ₀(n) je počet dělitelů n.

Vzorce zahrnující zlatý řez

Schneider^[25] našel dvojici identit spojujících funkci totientu, Zlatý řez a Möbiova funkce μ(n). V této části φ(n) je totientová funkce a ϕ = 1 + √5/2 = 1.618… je zlatý řez.

Oni jsou:

${ displaystyle phi = - součet _ {k = 1} ^ { infty} { frac { varphi (k)} {k}} log left (1 - { frac {1} { phi ^ {k}}} vpravo)}$

a

${ displaystyle { frac {1} { phi}} = - součet _ {k = 1} ^ { infty} { frac { mu (k)} {k}} log vlevo (1- { frac {1} { phi ^ {k}}} right).}$

Odečtením je dá

${ displaystyle sum _ {k = 1} ^ { infty} { frac { mu (k) - varphi (k)} {k}} log left (1 - { frac {1} { phi ^ {k}}} right) = 1.}$

Aplikováním exponenciální funkce na obě strany předchozí identity se získá nekonečný součinový vzorec pro E:

${ displaystyle e = prod _ {k = 1} ^ { infty} left (1 - { frac {1} { phi ^ {k}}} right) ! ! ^ { frac { mu (k) - varphi (k)} {k}}.}$

Důkaz je založen na dvou vzorcích

${ displaystyle { begin {aligned} sum _ {k = 1} ^ { infty} { frac { varphi (k)} {k}} left (- log left (1-x ^ { k} right) right) & = { frac {x} {1-x}} { text {and}} ; sum _ {k = 1} ^ { infty} { frac { mu (k)} {k}} left (- log left (1-x ^ {k} right) right) & = x, qquad quad { text {for}} 0$

Generování funkcí

The Dirichletova řada pro φ(n) mohou být psány ve smyslu Funkce Riemann zeta tak jako:^[26]

${ displaystyle sum _ {n = 1} ^ { infty} { frac { varphi (n)} {n ^ {s}}} = { frac { zeta (s-1)} { zeta (s)}}.}$

The Lambertova řada generující funkce je^[27]

${ displaystyle sum _ {n = 1} ^ { infty} { frac { varphi (n) q ^ {n}} {1-q ^ {n}}} = { frac {q} {( 1-q) ^ {2}}}}$

který konverguje pro |q| < 1.

Obojí dokazují elementární řady manipulací a vzorce pro φ(n).

Tempo růstu

Podle slov Hardyho a Wrighta, pořadí φ(n) je „vždy“ téměř n’.”^[28]

za prvé^[29]

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

ale jako n jde do nekonečna,^[30] pro všechny δ > 0

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

Tyto dva vzorce lze prokázat použitím o něco více než vzorců pro φ(n) a funkce dělitele součtu σ(n).

Ve skutečnosti, během dokazování druhého vzorce, nerovnost

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

platí pro n > 1, je prokázáno.

Také máme^[19]

${ displaystyle lim inf { frac { varphi (n)} {n}} log log n = e ^ {- gamma}.}$

Tady y je Eulerova konstanta, y = 0.577215665..., tak E^y = 1.7810724... a E^−y = 0.56145948....

Prokazování to zcela nevyžaduje věta o prvočísle.^[31][32] Od té doby log log n jde do nekonečna, tento vzorec to ukazuje

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

Ve skutečnosti platí více.^[33][34][35]

${ displaystyle varphi (n)> { frac {n} {e ^ { gamma} ; log log n + { frac {3} { log log n}}}} quad { text {for}} n> 2}$

a

${ displaystyle varphi (n) <{ frac {n} {e ^ { gamma} log log n}} quad { text {pro nekonečně mnoho}} n.}$

Druhou nerovnost ukázal Jean-Louis Nicolas. Ribenboim říká: „Metoda dokazování je zajímavá tím, že nerovnost je zobrazena nejprve za předpokladu, že Riemannova hypotéza je pravda, zadruhé za opačného předpokladu. ““^[35]

Pro průměrnou objednávku máme^[21][36]

${ 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 ,}$

kvůli Arnold Walfisz, což dokazuje využití odhadů na exponenciální částky kvůli I. M. Vinogradov a N. M. Korobov (toto je v současnosti nejznámější odhad tohoto typu). The "Velký Ó" znamená veličinu, která je omezena konstantním časem funkce n uvnitř závorek (což je ve srovnání s n²).

Tento výsledek lze použít k prokázání^[37] že pravděpodobnost relativně náhodných dvou náhodně vybraných čísel je 6/π².

Poměr po sobě jdoucích hodnot

V roce 1950 se ukázalo Somayajulu^[38][39]

${ 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 {zarovnáno}}}$

V roce 1954 Schinzel a Sierpiński posílil to, což dokazuje^[38][39] že ta sada

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

je hustý v kladných reálných číslech. Také prokázali^[38] že ta sada

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

je hustá v intervalu (0,1).

Totální čísla

A totient number je hodnota Eulerovy totientové funkce: tj m pro které existuje alespoň jeden n pro který φ(n) = m. The mocenství nebo multiplicita totient čísla m je počet řešení této rovnice.^[40] A nereceptivní je přirozené číslo, které není totientovým číslem. Každé liché celé číslo přesahující 1 je triviálně nontotentní. Existuje také nekonečně mnoho dokonce i neototientů,^[41] a každé kladné celé číslo má násobek, který je dokonce nontotentní.^[42]

Počet celkových čísel až do daného limitu X je

${ displaystyle { frac {x} { log x}} e ^ {{ big (} C + o (1) { big)} ( log log log x) ^ {2}}}$

pro konstantu C = 0.8178146....^[43]

Pokud se počítá podle multiplicity, počet celkových čísel až do daného limitu X je

${ displaystyle { Big vert} {n: phi (n) leq x } { Big vert} = { frac { zeta (2) zeta (3)} { zeta (6 )}} cdot x + R (x)}$

kde chybový termín R je maximálně v pořádku X/(log X)^k pro všechny pozitivní k.^[44]

Je známo, že rozmanitost m překračuje m^δ nekonečně často pro všechny δ < 0.55655.^[45][46]

Fordova věta

Ford (1999) dokázal, že pro každé celé číslo k ≥ 2 existuje totient číslo m multiplicity k: to znamená, pro které rovnice φ(n) = m má přesně k řešení; tento výsledek předtím předpokládal Wacław Sierpiński,^[47] a bylo získáno v důsledku Schinzelova hypotéza H.^[43] Každá multiplicita, která nastane, tak činí nekonečně často.^[43][46]

Žádné číslo m je znáno s četností k = 1. Carmichaelův dohad o totientní funkci je prohlášení, že takové neexistuje m.^[48]

Dokonalá čísla totientů

Aplikace

Cyklomtomie

V poslední části Disquisitiones^[49][50] Gauss dokazuje^[51] že pravidelný n-gon může být konstruován s pravítkem a kompasem, pokud φ(n) je síla 2. Pokud n je síla lichého prvočísla, vzorec pro totient říká, že jeho totient může být mocninou dvou, pouze pokud n je první síla a n − 1 je mocnina 2. Vyzvou se prvočísla, která jsou o více než mocnina 2 Fermat připraví a je známo pouze pět: 3, 5, 17, 257 a 65537. Fermat a Gauss o nich věděli. Nikdo nebyl schopen prokázat, zda ještě existují.

Tedy pravidelný n-gon má konstrukci pravítka a kompasu, pokud n je produktem zřetelných Fermatových prvočísel a jakékoli síly 2. Prvních pár takových n jsou^[52]

2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 17, 20, 24, 30, 32, 34, 40, ... (sekvence A003401 v OEIS ).

Kryptosystém RSA

Nastavení systému RSA zahrnuje výběr velkých prvočísel p a q, výpočetní n = pq a k = φ(n)a nalezení dvou čísel E a d takhle vyd ≡ 1 (mod k). Čísla n a E („šifrovací klíč“) jsou zveřejňovány a d („dešifrovací klíč“) je soukromý.

Zpráva představovaná celým číslem m, kde 0 < m < n, je šifrován výpočtem S = m^E (mod n).

Je dešifrován výpočtem t = S^d (mod n). Eulerovu větu lze použít k prokázání, že pokud 0 < t < n, pak t = m.

Zabezpečení systému RSA by bylo ohroženo, pokud by to bylo číslo n lze započítat, nebo pokud φ(n) lze vypočítat bez faktoringu n.

Nevyřešené problémy

Lehmerova domněnka

Li p je tedy prime φ(p) = p − 1. V roce 1932 D. H. Lehmer zeptal se, jestli existují nějaká složená čísla n takhle φ(n) rozděluje n − 1. Žádné nejsou známy.^[53]

V roce 1933 dokázal, že pokud existuje n existuje, musí být liché, bez čtverců a dělitelné nejméně sedmi prvočísel (tj. ω(n) ≥ 7). V roce 1980 to Cohen a Hagis dokázali n > 10²⁰ a to ω(n) ≥ 14.^[54] Dále Hagis ukázal, že pokud 3 rozdělí n pak n > 10^1937042 a ω(n) ≥ 298848.^[55][56]

Carmichaelova domněnka

To znamená, že neexistuje žádné číslo n s vlastností, že pro všechna ostatní čísla m, m ≠ n, φ(m) ≠ φ(n). Vidět Fordova věta výše.

Jak je uvedeno v hlavním článku, existuje-li jediný protiklad k této domněnce, musí existovat nekonečně mnoho protikladů a ten nejmenší má v základně 10 alespoň deset miliard číslic.^[40]

Viz také

• Funkce Carmichael
• Duffin – Schaefferova domněnka
• Zobecnění Fermatovy malé věty
• Vysoce složené číslo
• Multiplikativní skupina celých čísel modulo n
• Ramanujan součet
• Totální součtová funkce

Poznámky

Reference

externí odkazy

• "Totient function", Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
• Eulerova funkce Phi a věta o čínském zbytku - důkaz toho φ(n) je multiplikativní
• Eulerova kalkulačka funkcí totientu v JavaScriptu - až 20 číslic
• Dineva, Rosica, Funkce Euler Totient, Möbius a dělitel
• Plytage, Loomis, Polhill Shrnutí funkce Euler Phi