Funkcja Carmichaela

Funkcja λ (lambda) Carmichaela – funkcja określona dla dodatnich liczb całkowitych, której wartością dla danej liczby ${\displaystyle n}$ jest najmniejsza liczba, taka, że podniesiona do jej potęgi liczba względnie pierwsza z ${\displaystyle n}$ przystaje do ${\displaystyle 1\operatorname {mod} n,}$ przy czym ${\displaystyle \lambda (0)=0}$^[1][2].

${\displaystyle \forall _{k<n}\left[{\mbox{NWD}}(k,n)=1\Rightarrow k^{\lambda (n)}\operatorname {mod} n=1\right],}$

gdzie NWD to największy wspólny dzielnik, a „${\displaystyle \operatorname {mod} n}$” – reszta z dzielenia przez ${\displaystyle n.}$

Definicja formalna

Ścisła definicja funkcji Carmichaela jest taka, że dla danej liczby ${\displaystyle n,}$ ${\displaystyle \lambda \ (n)}$ to najmniejsza taka liczba, że:

${\displaystyle \forall _{k<n,\ NWD(k,n)=1}\ k^{\lambda (n)}\operatorname {mod} n=1,}$

gdzie NWD to największy wspólny dzielnik, a „${\displaystyle \operatorname {mod} n}$” – reszta z dzielenia przez ${\displaystyle n.}$

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 ${\displaystyle (Z_{n}^{*})}$ z działaniem mnożenia modulo n to:

${\displaystyle \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

Poniżej ${\displaystyle \lambda }$ – oznacza funkcję Carmichaela, ${\displaystyle \phi }$ – funkcję Eulera.

Ścisły wzór

Ścisły wzór na funkcję λ jest następujący (w poniższym wzorze p_i to dla różnych indeksów różne liczby pierwsze, a α_i – liczby naturalne):

${\displaystyle \lambda (n)=\left\{{\begin{array}{cl}\phi (n)&n=p_{i}^{\alpha _{i}},\ p_{i}>2\lor \alpha _{i}<3\\{\frac {\phi (n)}{2}}&n=2^{\alpha _{i}},\ \alpha _{i}>2\\NWW{\big (}\lambda (p_{1}^{\alpha _{1}}),\dots ,\lambda (p_{k}^{\alpha _{k}}){\big )}&n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}\end{array}}\right.,}$

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

Oszacowania

Dla dowolnej liczby naturalnej ${\displaystyle k}$ zachodzi oszacowanie górne:

${\displaystyle \lambda (k)\leqslant \phi (k).}$

Natomiast zachodzi również nietrywialne oszacowanie górne dla nieskończenie wielu ${\displaystyle n{:}}$

${\displaystyle \lambda (n)<\ln(n)^{3,24\log _{3}n}}$

i oszacowanie dolne dla dostatecznie dużych ${\displaystyle n{:}}$

${\displaystyle \lambda (n)>\ln(n)^{1,44\log _{3}n}.}$

Wartości dla potęg liczby dwa^[3]

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

${\displaystyle \lambda (2^{n})=\phi (2^{n})}$ dla ${\displaystyle 0\leqslant n\leqslant 2,}$

${\displaystyle \lambda (2^{n})=2^{n-2}={\frac {\phi (2^{n})}{2}}}$ dla ${\displaystyle n\geqslant 3.}$

Wartość dla liczb pierwszych

Jeżeli ${\displaystyle p}$ – liczba pierwsza to zachodzi:

${\displaystyle \lambda (p)=\phi (p)=p-1.}$

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

Jeżeli ${\displaystyle p}$ – nieparzysta liczba pierwsza a ${\displaystyle k}$ – liczba naturalna to zachodzi:

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

Wartość dla iloczynu liczb względnie pierwszych

Niech ${\displaystyle p,}$${\displaystyle q}$ – dwie liczby naturalne; wówczas:

${\displaystyle NWD(p,q)=1\Rightarrow \lambda (pq)=NWW{\big (}\lambda (p),\lambda (q){\big )}.}$

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

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

• ${\displaystyle \lambda (n)\ |\ (n-1),}$
• ${\displaystyle \forall _{a\in \mathbb {N} }\ NWD(a,n)=1\Rightarrow a^{n-1}\equiv 1\ (\operatorname {mod} n).}$

Przykład zastosowania funkcji Carmichaela

Problem: obliczyć ${\displaystyle 3^{2000}\operatorname {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 Carmichaela. λ(248)=NWW(λ(8),λ(31))=NWW(4, 30)=30. Tak więc – ${\displaystyle 3^{30}\operatorname {mod} 248=1.}$ Co więcej – ponieważ 30 „mieści się” w 2000 66 razy to zachodzi:

${\displaystyle 3^{2000}\operatorname {mod} 248=((3^{30})^{66})(3^{20})\operatorname {mod} 248=(1^{66})(3^{20})\operatorname {mod} 248=3^{20}\operatorname {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 3⁵=243 co, rozważając działanie ${\displaystyle \operatorname {mod} 248}$ jest równoważne wartości ${\displaystyle -5(243=248-5).}$ Czyli:

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

Funkcja Carmichaela i funkcja Eulera

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.

${\displaystyle \phi (105)=\phi (3\cdot 5\cdot 7)=\phi (3)\phi (5)\phi (7)=2\cdot 4\cdot 6=48,}$

${\displaystyle \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

Wykres funkcji dla przedziału <1;23>

Wartości dla 7 najmniejszych liczb Carmichaela

Zobacz też

• chińskie twierdzenie o resztach
• funkcja φ Eulera
• liczby Carmichaela
• małe twierdzenie Fermata
• RSA

Przypisy

Bibliografia

• Paul Erdős, Carl Pomerance, Eric Schmutz, Carmichael’s lambda function, Acta Arithmetica, vol. 58, s. 363–385, 1991.
• John Friedlander, Carl Pomerance, Igor E. Shparlinski, Period of the power generator and small values of the Carmichael function, Mathematics of Computation, vol. 70 no. 236, s. 1591–1605, 2001.