Funkcja Carmichaela
Funkcja λ (lambda) Carmichaela – funkcja określona dla dodatnich liczb całkowitych, której wartością dla danej liczby jest najmniejsza liczba, taka, że podniesiona do jej potęgi liczba względnie pierwsza z przystaje do przy czym [1][2].
gdzie NWD to największy wspólny dzielnik, a „” – reszta z dzielenia przez
Definicja formalna
Formalnie, dla danej liczby to najmniejsza taka liczba, że:
gdzie NWD to największy wspólny dzielnik, a „” – reszta z dzielenia przez
Wychodząc od pojęcia grupy, pojęcie funkcji Carmichaela można wprowadzić dużo naturalniej. Mianowicie, jeżeli rozważymy multiplikatywną grupę klas reszt modulo n z działaniem mnożenia modulo n to:
przy czym powyższe potęgowanie należy rozumieć jako składanie działania z grupy.
Własności
Poniżej – oznacza funkcję Carmichaela, – funkcję Eulera.
Ścisły wzór
Ścisły wzór na funkcję λ jest następujący (w poniższym wzorze pi to dla różnych indeksów różne liczby pierwsze, a αi – liczby naturalne):
przy czym NWW to najmniejsza wspólna wielokrotność.
Oszacowania
Dla dowolnej liczby naturalnej prawdziwe jest oszacowanie górne:
Dla dowolnej stałej dla dostatecznie dużych zachodzi nietrywialne ograniczenie:
Z drugiej strony dla pewnej stałej i nieskończenie wielu zachodzi
Wartości dla potęg liczby dwa[4]
Dla potęg liczby dwa zachodzą następujące równości:
- dla
- dla
Wartość dla liczb pierwszych
Jeżeli – liczba pierwsza to zachodzi:
Wartość dla potęg nieparzystych liczb pierwszych[4]
Jeżeli – nieparzysta liczba pierwsza a – liczba naturalna to zachodzi:
Wartość dla iloczynu liczb względnie pierwszych
Niech – dwie liczby naturalne; wówczas:
Twierdzenie Carmichaela – związek funkcji z Małym Twierdzeniem Fermata
tzw. Twierdzenie Carmichaela mówi, że następujące dwa warunki są równoważne:
Przykład zastosowania funkcji Carmichaela
Problem: obliczyć
Rozwiązanie: ponieważ 248 i 3 są względnie pierwsze (248 nie dzieli się przez 3, bo 2+4+8=14 a 1+4=5 → cecha podzielności przez 3), to możemy skorzystać z właściwości funkcji Carmichaela. λ(248)=NWW(λ(8),λ(31))=NWW(4, 30)=30. Tak więc – Co więcej – ponieważ 30 „mieści się” w 2000 66 razy to zachodzi:
co jest już do policzenia znacznie prostsze. Jeżeli nie dysponujemy kalkulatorem to możemy skorzystać z prostej właściwości – mianowicie 35=243 co, rozważając działanie jest równoważne wartości Czyli:
Funkcja Carmichaela i funkcja Eulera
Ponieważ patrząc w odpowiedni sposób na funkcję Eulera, obie ww. funkcje pełnią podobną funkcję (tzn. są uniwersalnym wykładnikiem, dającym dla podstaw względnie pierwszych z argumentem, wartość przystającą do 1), to warto zobaczyć jaki jest realny zysk wartości. Np.
Oszczędność jest więc wyraźna.
Wartości dla 25 początkowych liczb naturalnych
1. | 2. | 3. | 4. | 5. | 6. | 7. | 8. | 9. | 10. | 11. | 12. | 13. | 14. | 15. | 16. | 17. | 18. | 19. | 20. | 21. | 22. | 23. | 24. | 25. |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 2 | 2 | 4 | 2 | 6 | 2 | 6 | 4 | 10 | 2 | 12 | 6 | 4 | 4 | 16 | 6 | 18 | 4 | 6 | 10 | 22 | 2 | 20 |
Wartości dla 7 najmniejszych liczb Carmichaela
561. | 1105. | 1729. | 2465. | 2821. | 6601. | 8911. |
---|---|---|---|---|---|---|
80 | 48 | 36 | 112 | 60 | 1320 | 198 |
Zobacz też
- chińskie twierdzenie o resztach
- funkcja φ Eulera
- liczby Carmichaela
- małe twierdzenie Fermata
- RSA
Przypisy
- ↑ Carmichael lambda function: Primary definition [online], functions.wolfram.com [dostęp 2017-10-13] .
- ↑ Carmichael lambda function: Zeros [online], functions.wolfram.com [dostęp 2017-10-13] .
- ↑ a b PaulP. Erdős PaulP., CarlC. Pomerance CarlC., EricE. Schmutz EricE., Carmichael’s lambda function, „Acta Arithmetica”, 58 (4), 1991, s. 363–385, ISSN 0065-1036 [dostęp 2024-01-22] .
- ↑ a b Carmichael lambda function: Specific values (subsection 03/01) [online], functions.wolfram.com [dostęp 2017-10-13] .
Bibliografia
- Paul Erdős, Carl Pomerance, Eric Schmutz, Carmichael’s lambda function, Acta Arithmetica, vol. 58, s. 363–385, 1991.
- John Friedlander, Carl Pomerance, Igor E. Shparlinski, Period of the power generator and small values of the Carmichael function, Mathematics of Computation, vol. 70 no. 236, s. 1591–1605, 2001.
- p
- d
- e
pojęcia definiujące |
| ||||
---|---|---|---|---|---|
typy ciągów |
| ||||
przykłady ciągów liczb naturalnych | |||||
inne przykłady ciągów liczb | |||||
twierdzenia |
| ||||
powiązane pojęcia |