Funkcja Carmichaela

Funkcja λ (lambda) Carmichaela – funkcja 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 $λ (0) = 0$ ^[1]^[2].

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

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

Definicja formalna

Formalnie, dla danej liczby $n,$ $λ (n)$ to najmniejsza taka liczba, że:

\forall_{k < n, N W D (k, n) = 1} k^{λ (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 Carmichaela 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:

λ (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 $λ$ – oznacza funkcję Carmichaela, $ϕ$ – 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):

λ (n) = {\begin{matrix} ϕ (n) & n = p_{i}^{α_{i}}, p_{i} > 2 \lor α_{i} < 3 \\ \frac{ϕ (n)}{2} & n = 2^{α_{i}}, α_{i} > 2 \\ N W W (λ (p_{1}^{α_{1}}), \dots, λ (p_{k}^{α_{k}})) & n = \prod_{i = 1}^{k} p_{i}^{α_{i}} \end{matrix},

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

Oszacowania

Dla dowolnej liczby naturalnej $k$ prawdziwe jest oszacowanie górne:

λ (k) ⩽ ϕ (k) .

Dla dowolnej stałej $c < \frac{1}{\ln 2},$ dla dostatecznie dużych $n$ zachodzi nietrywialne ograniczenie:

λ (n) > \ln (n)^{c \ln \ln \ln n} .

^[3]

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

λ (n) < \ln (n)^{c^{'} \ln \ln \ln n} .

^[3]

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

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

λ (2^{n}) = ϕ (2^{n})

dla

0 ⩽ n ⩽ 2,

λ (2^{n}) = 2^{n - 2} = \frac{ϕ (2^{n})}{2}

dla

n ⩾ 3 .

Wartość dla liczb pierwszych

Jeżeli $p$ – liczba pierwsza to zachodzi:

λ (p) = ϕ (p) = p - 1 .

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

Jeżeli $p$ – nieparzysta liczba pierwsza a $k$ – liczba naturalna to zachodzi:

λ (p^{k}) = p^{k - 1} (p - 1) = ϕ (p^{k}) .

Wartość dla iloczynu liczb względnie pierwszych

Niech $p,$ $q$ – dwie liczby naturalne; wówczas:

N W D (p, q) = 1 \Rightarrow λ (p q) = N W W (λ (p), λ (q)) .

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:

$λ (n) | (n - 1),$
$\forall_{a \in ℕ} N W D (a, n) = 1 \Rightarrow a^{n - 1} \equiv 1 (\mod n) .$

Przykład zastosowania funkcji Carmichaela

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 Carmichaela. λ(248)=NWW(λ(8),λ(31))=NWW(4, 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 3⁵=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 = 2 5^{2} \mod 248 = 625 \mod 248 = 129 .