Funkcja Carmichaela

funkcja arytmetyczna zdefiniowana implikacją

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

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

Poniżej   – oznacza funkcję Carmichaela,  funkcję Eulera.

Ścisły wzór edytuj

Ś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

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

Dla potęg liczby dwa zachodzą następujące równości:

  dla  
  dla  

Wartość dla liczb pierwszych edytuj

Jeżeli   – liczba pierwsza to zachodzi:

 

Wartość dla potęg nieparzystych liczb pierwszych[4] edytuj

Jeżeli   – nieparzysta liczba pierwsza a   – liczba naturalna to zachodzi:

 

Wartość dla iloczynu liczb względnie pierwszych edytuj

Niech    – dwie liczby naturalne; wówczas:

 

Twierdzenie Carmichaela – związek funkcji z Małym Twierdzeniem Fermata edytuj

tzw. Twierdzenie Carmichaela mówi, że następujące dwa warunki są równoważne:

  •  
  •  

Przykład zastosowania funkcji Carmichaela edytuj

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

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

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

561. 1105. 1729. 2465. 2821. 6601. 8911.
80 48 36 112 60 1320 198

Zobacz też edytuj

Przypisy edytuj

  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