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.

\forall_{k<n} \big[\mbox{NWD}(k,n)=1 \Rightarrow k^{\lambda(n)}\mbox{mod } n = 1\big]

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

Definicja formalna[edytuj | edytuj kod]

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


\forall_{k<n,\ NWD(k,n)=1}\ k^{\lambda(n)}\ mod\ n = 1

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_n^*) z działaniem mnożenia modulo n to:

\lambda(n) = \min \{ k : \forall_{x \in Z_n^*}\ x^k \equiv 1 \}

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):


\lambda(n) = \left\{
\begin{matrix}
\phi(n) & n=p_i^{\alpha_i},\ p_i>2 \or \alpha_i<3 \\
\frac{\phi(n)}{2} & n=2^{\alpha_i},\ \alpha_i>2 \\
NWW \big(\phi(p_1^{\alpha_1}),\ldots,\phi(p_k^{\alpha_k})\big) & n=\prod_{i=1}^{k}p_i^{\alpha_i}
\end{matrix} \right.

przy czym φ - funkcja Eulera, a NWW - Najmniejsza wspólna wielokrotność.

Oszacowania[edytuj | edytuj kod]

Dla dowolnej liczby naturalnej k zachodzi oszacowanie górne:

\lambda(k) \leqslant \phi(k)

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

\lambda(n) < \ln(n)^{3,24\log_3n}

i oszacowanie dolne dla dostatecznie dużych n:

\lambda(n) > \ln(n)^{1.44\log_3n}

Wartość dla liczb pierwszych[edytuj | edytuj kod]

Jeżeli p - liczba pierwsza to zachodzi:

\lambda(p) = \phi(p) = p-1

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

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

\lambda(p^k) = p^{k-1}(p-1) = \phi(p^k)

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

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

NWD(p,q)=1 \Rightarrow \lambda(pq)=NWW\big(\lambda(p),\lambda(q)\big)

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

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

  •  \lambda(n)\ |\ (n-1)
  •  \forall_{a \in \mathbb{N}}\ NWD(a,n)=1 \Rightarrow a^{n-1} \equiv 1\ (mod\ n)

Przykład zastosowania funkcji Carmichaëla[edytuj | edytuj kod]

Problem: obliczyć 3^{2000}\ mod\ 248

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 - 3^{30}\ mod\ 248=1. Co więcej - ponieważ 30 "mieści się" w 2000 66 razy to zachodzi:

3^{2000}\ mod\ 248=((3^{30})^{66})(3^{20})\ mod\ 248=(1^{66})(3^{20})\ mod\ 248=3^{20}\ mod\ 248

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:

 3^{20}\ mod\ 248 = ((3^5)^4)\ mod\ 248 = (-5)^4\ mod\ 248 = 25^2\ mod\ 248 = 625\ mod\ 248=129

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

\phi(105)=\phi(3\cdot5\cdot7)=\phi(3)\phi(5)\phi(7)=2\cdot4\cdot6=48

\lambda(105)=NWW\big(\lambda(3),\lambda(5),\lambda(7)\big)=NWW(2,4,6)=12

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 Carmichaëla[edytuj | edytuj kod]

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

Bibliografia[edytuj | edytuj kod]

Zobacz też[edytuj | edytuj kod]