Przejdź do zawartości

Funkcja Carmichaela

Z Wikipedii, wolnej encyklopedii

Funkcja λ (lambda) Carmichaelafunkcja 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 αiliczby 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:

[3]

Z drugiej strony dla pewnej stałej i nieskończenie wielu zachodzi

[3]

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
Wykres funkcji dla przedziału <1;23>

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]
  1. Carmichael lambda function: Primary definition [online], functions.wolfram.com [dostęp 2017-10-13].
  2. Carmichael lambda function: Zeros [online], functions.wolfram.com [dostęp 2017-10-13].
  3. 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].
  4. a b Carmichael lambda function: Specific values (subsection 03/01) [online], functions.wolfram.com [dostęp 2017-10-13].

Bibliografia

[edytuj | edytuj kod]