Funkcja Carmichaela
Funkcja λ (lambda) Carmichaela – funkcja określona dla dodatnich liczb całkowitych, której wartością dla danej liczby n jest najmniejsza liczba, taka, że podniesiona do jej potęgi liczba względnie pierwsza z n przystaje do 1 mod n, przy czym [1][2].
gdzie NWD to największy wspólny dzielnik, a „” – reszta z dzielenia przez
Spis treści
- 1 Definicja formalna
- 2 Własności
- 3 Twierdzenie Carmichaela – związek funkcji z Małym Twierdzeniem Fermata
- 4 Przykład zastosowania funkcji Carmichaela
- 5 Funkcja Carmichaela i funkcja Eulera
- 6 Wartości dla 25 początkowych liczb naturalnych
- 7 Wartości dla 7 najmniejszych liczb Carmichaela
- 8 Zobacz też
- 9 Przypisy
- 10 Bibliografia
Definicja formalna[edytuj | edytuj kod]
Ścisła definicja funkcji Carmichaela jest taka, że dla danej liczby n, λ(n) 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ę Carmichaёla, – 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 k zachodzi oszacowanie górne:
Natomiast zachodzi również nietrywialne oszacowanie górne dla nieskończenie wielu :
i oszacowanie dolne dla dostatecznie dużych :
Wartości dla potęg liczby dwa[3][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 p – liczba pierwsza to zachodzi:
Wartość dla potęg nieparzystych liczb pierwszych[3][edytuj | edytuj kod]
Jeżeli p – nieparzysta liczba pierwsza a k – liczba naturalna to zachodzi:
Wartość dla iloczynu liczb względnie pierwszych[edytuj | edytuj kod]
Niech p,q – 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(2, 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 mod 248 jest równoważne wartości -5 (243=248-5). 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 |
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, functions.wolfram.com [dostęp 2017-10-13] .
- ↑ Carmichael lambda function: Zeros, functions.wolfram.com [dostęp 2017-10-13] .
- ↑ a b Carmichael lambda function: Specific values (subsection 03/01), 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, 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.