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
[edytuj | edytuj kod]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
[edytuj | edytuj kod]Poniżej – oznacza funkcję Carmichaela, – funkcję Eulera.
Ścisły wzór
[edytuj | edytuj kod]Ś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
[edytuj | edytuj kod]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]
[edytuj | edytuj kod]Dla potęg liczby dwa zachodzą następujące równości:
- dla
- dla
Wartość dla liczb pierwszych
[edytuj | edytuj kod]Jeżeli – liczba pierwsza to zachodzi:
Wartość dla potęg nieparzystych liczb pierwszych[4]
[edytuj | edytuj kod]Jeżeli – nieparzysta liczba pierwsza a – liczba naturalna to zachodzi:
Wartość dla iloczynu liczb względnie pierwszych
[edytuj | edytuj kod]Niech – dwie liczby naturalne; wówczas:
Twierdzenie Carmichaela – związek funkcji z Małym Twierdzeniem Fermata
[edytuj | edytuj kod]tzw. Twierdzenie Carmichaela mówi, że następujące dwa warunki są równoważne:
Przykład zastosowania funkcji Carmichaela
[edytuj | edytuj kod]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
[edytuj | edytuj kod]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
[edytuj | edytuj kod]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 |
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/1/15/Funkcja_Carmichaela.svg/500px-Funkcja_Carmichaela.svg.png)
Wartości dla 7 najmniejszych liczb Carmichaela
[edytuj | edytuj kod]561. | 1105. | 1729. | 2465. | 2821. | 6601. | 8911. |
---|---|---|---|---|---|---|
80 | 48 | 36 | 112 | 60 | 1320 | 198 |
Zobacz też
[edytuj | edytuj kod]Przypisy
[edytuj | edytuj kod]- ↑ 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 Paul Erdős , Carl Pomerance , Eric Schmutz , 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
[edytuj | edytuj kod]- 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.