Funkcja Carmichaela

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Funkcja λ Carmichaëlafunkcja 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.

gdzie NWD to największy wspólny dzielnik a "mod n" - reszta z dzielenia przez n.

Definicja formalna[edytuj]

Ścisła definicja funkcji Carmichaëla jest taka, że dla danej liczby n, λ(n) to najmniejsza taka liczba, że:

gdzie NWD to największy wspólny dzielnik a "mod n" - reszta z dzielenia przez n.

Wychodząc od pojęcia grupy, pojęcie funkcji Carmichaëla 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ę Carmichaёla, – 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 αi - liczby naturalne):

przy czym NWW to Najmniejsza wspólna wielokrotność.

Oszacowania[edytuj]

Dla dowolnej liczby naturalnej k zachodzi oszacowanie górne:

Natomiast zachodzi również nietrywialne oszacowanie górne dla nieskończenie wielu n:

i oszacowanie dolne dla dostatecznie dużych n:

Wartość dla liczb pierwszych[edytuj]

Jeżeli p - liczba pierwsza to zachodzi:

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

jeżeli p - nieparzysta liczba pierwsza a k - liczba naturalna to zachodzi:

Wartość dla iloczynu liczb względnie pierwszych[edytuj]

niech p,q - dwie liczby naturalne; wówczas:

Twierdzenie Carmichaëla - związek funkcji z Małym Twierdzeniem Fermata[edytuj]

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

Przykład zastosowania funkcji Carmichaëla[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 Carmichaëla. λ(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 Carmichaëla 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 Carmichaëla[edytuj]

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

Bibliografia[edytuj]

Zobacz też[edytuj]