Funkcja Carmichaela

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

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

Bibliografia[edytuj | edytuj kod]