Carmichaelsova domněnka o funkci totient - Carmichaels totient function conjecture - Wikipedia

V matematice Carmichaelův dohad o totientní funkci týká se multiplicita hodnot Eulerova totientová funkce φ(n), který počítá počet celých čísel menší než a coprime na n. Uvádí se v něm, že pro každého n existuje alespoň jedno další celé číslo m ≠ n takhle φ(m) = φ(n).Robert Carmichael nejprve uvedl toto dohad v roce 1907, ale jako teorém spíše než jako dohad. Nicméně, jeho důkaz byl vadný, a v roce 1922, on stáhl jeho požadavek a uvedl domněnku jako otevřený problém.

Příklady

Funkce totient φ(n) se rovná 2, když n je jedna ze tří hodnot 3, 4 a 6. Pokud tedy vezmeme kteroukoli z těchto tří hodnot jako n, pak kteroukoli z dalších dvou hodnot lze použít jako m pro který φ(m) = φ(n).

Podobně je totient roven 4, když n je jednou ze čtyř hodnot 5, 8, 10 a 12 a je rovna 6, když n je jedna ze čtyř hodnot 7, 9, 14 a 18. V každém případě existuje více než jedna hodnota n se stejnou hodnotou φ(n).

Domněnka tvrdí, že tento jev opakovaných hodnot platí pro všechnyn.

Dolní hranice

Jsou velmi vysoké dolní hranice pro Carmichaelovu domněnku, kterou lze relativně snadno určit. Sám Carmichael dokázal, že jakýkoli protiklad jeho domněnky (tj. Hodnota n takové, že φ (n) se liší od totientů všech ostatních čísel) musí být alespoň 10³⁷, a Victor Klee prodloužil tento výsledek na 10⁴⁰⁰. Dolní mez ${ displaystyle 10 ^ {10 ^ {7}}}$byla dána Schlaflyem a Wagonem a dolní mezí ${ displaystyle 10 ^ {10 ^ {10}}}$ byl určen Kevin Ford v roce 1998.^[1]

Výpočtová technika, která je základem těchto dolních mezí, závisí na některých klíčových výsledcích Klee, které umožňují ukázat, že nejmenší protipříklad musí být dělitelný druhou mocninou prvočísel dělících jeho celkovou hodnotu. Výsledky Klee naznačují, že 8 a Fermatova prvočísla (prvočísla formy 2^k + 1) kromě 3 nerozdělujte nejmenší protiklad. V důsledku toho je prokázání domněnky ekvivalentní prokázání, že domněnka platí pro všechna celá čísla shodná se 4 (mod 8).

Další výsledky

Ford také dokázal, že pokud existuje protiklad k domněnce, pak pozitivní podíl (ve smyslu asymptotické hustoty) celých čísel jsou rovněž protiklady.^[1]

Ačkoli se domněnce široce věří, Carl Pomerance dal dostatečnou podmínku pro celé číslo n být protikladem k domněnce (Pomerance 1974 ). Podle této podmínky n je protikladem pro každý prime p takhle p - 1 rozdělí φ(n), p² rozdělujen. Pomerance však ukázala, že existence takového celého čísla je vysoce nepravděpodobná. V zásadě lze ukázat, že pokud je první k připraví p shodné s 1 (modq) (kde q je prvočíslo) jsou všechny menší než q^k+1, pak takové celé číslo bude dělitelné každým prvočíslem, a proto nemůže existovat. V každém případě je prokázání toho, že Pomeranceův protiklad neexistuje, zdaleka neprokazovat Carmichaelovu domněnku. Pokud však existuje, existuje nekonečně mnoho protikladů, jak tvrdí Ford.

Dalším způsobem, jak uvést Carmichaelovu domněnku, je, že pokudA(F) označuje počet kladných celých čísel n pro který φ(n) = F, pak A(F) se nikdy nemůže rovnat 1. Podobně, Wacław Sierpiński domníval se, že každé kladné celé číslo jiné než 1 se vyskytuje jako hodnota A (F), domněnka, kterou v roce 1999 dokázal Kevin Ford.^[2]

Poznámky

Reference

• Carmichael, R. D. (1907), „On Euler's φ-funkce", Bulletin of the American Mathematical Society, 13 (5): 241–243, doi:10.1090 / S0002-9904-1907-01453-2, PAN  1558451.
• Carmichael, R. D. (1922), „Poznámka k Eulerovi φ-funkce", Bulletin of the American Mathematical Society, 28 (3): 109–110, doi:10.1090 / S0002-9904-1922-03504-5, PAN  1560520.
• Ford, K. (1999), „The number of solutions of φ(X) = m", Annals of Mathematics, 150 (1): 283–311, doi:10.2307/121103, JSTOR  121103, PAN  1715326, Zbl  0978.11053.
• Guy, Richard K. (2004), Nevyřešené problémy v teorii čísel (3. vyd.), Springer-Verlag, B39, ISBN  978-0-387-20860-2, Zbl  1058.11001.
• Klee, V. L., Jr. (1947), „O domněnce Carmichaela“, Bulletin of the American Mathematical Society, 53 (12): 1183–1186, doi:10.1090 / S0002-9904-1947-08940-0, PAN  0022855, Zbl  0035.02601.
• Pomerance, Carle (1974), „O Carmichaelově domněnce“ (PDF), Proceedings of the American Mathematical Society, 43 (2): 297–298, doi:10.2307/2038881, JSTOR  2038881, Zbl  0254.10009.
• Sándor, Jozsef; Crstici, Borislav (2004), Příručka teorie čísel II, Dordrecht: Kluwer Academic, s. 228–229, ISBN  978-1-4020-2546-4, Zbl  1079.11001.
• Schlafly, A .; Wagon, S. (1994), „Carmichaelova domněnka o Eulerově funkci platí pod 10^10,000,000", Matematika výpočtu, 63 (207): 415–419, doi:10.2307/2153585, JSTOR  2153585, PAN  1226815, Zbl  0801.11001.

externí odkazy

• Weisstein, Eric W. „Domněnka totálních funkcí Carmichaela“. MathWorld.