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

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

Formalnie, dla danej liczby${\displaystyle n,}$${\displaystyle \lambda (n)}$ to najmniejsza taka liczba, że:

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

Wychodząc od pojęciagrupy, pojęcie funkcji Carmichaela można wprowadzić dużo naturalniej. Mianowicie, jeżeli rozważymymultiplikatywną grupę klas reszt modulo n${\displaystyle (Z_n^{\ast })}$ z działaniem mnożenia modulo n to:

${\displaystyle \lambda (n)=min\{k:{\mathrm{\forall }}_{x\in Z_n^{\ast }}{x}^k\equiv 1\},}$

przy czym powyższe potęgowanie należy rozumieć jako składanie działania z grupy.

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

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

przy czym NWW tonajmniejsza wspólna wielokrotność.

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

${\displaystyle \lambda (k)⩽\varphi (k).}$

Dla dowolnej stałej dla dostatecznie dużych${\displaystyle n}$ zachodzi nietrywialne ograniczenie:

${\displaystyle \lambda (n)>\ln (n{)}^{c\ln \ln \ln n}.}$^[3]

Z drugiej strony dla pewnej stałej${\displaystyle c^{\prime }}$ i nieskończenie wielu${\displaystyle n}$ zachodzi

^[3]

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

${\displaystyle \lambda (2^n)=\varphi (2^n)}$ dla${\displaystyle 0⩽n⩽2,}$

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

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

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

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

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

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

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

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

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

Problem: obliczyć${\displaystyle 3^{2000}\mathrm{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}\mathrm{mod}248=1.}$ Co więcej – ponieważ 30 „mieści się” w 2000 66 razy to zachodzi:

${\displaystyle 3^{2000}\mathrm{mod}248=((3^{30}{)}^{66})(3^{20})\mathrm{mod}248=(1^{66})(3^{20})\mathrm{mod}248=3^{20}\mathrm{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 \mathrm{mod}248}$ jest równoważne wartości${\displaystyle -5(243=248-5).}$ Czyli:

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

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 \varphi (105)=\varphi (3\cdot 5\cdot 7)=\varphi (3)\varphi (5)\varphi (7)=2\cdot 4\cdot 6=48,}$

${\displaystyle \lambda (105)=NWW(\lambda (3),\lambda (5),\lambda (7))=NWW(2,4,6)=12.}$

Oszczędność jest więc wyraźna.

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

• 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.

• Funkcje arytmetyczne
• Arytmetyka modularna

• Szablon cytowania zamienił nazwę czasopisma