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

\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} .

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

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

Wartości dla potęg liczby dwa

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

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

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.

ϕ (105) = ϕ (3 \cdot 5 \cdot 7) = ϕ (3) ϕ (5) ϕ (7) = 2 \cdot 4 \cdot 6 = 48,

λ (105) = N W W (λ (3), λ (5), λ (7)) = N W W (2, 4, 6) = 12.

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

Wartości dla 25 początkowych liczb naturalnych

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

Wartości dla 7 najmniejszych liczb Carmichaela

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

Zobacz też

Przypisy

↑ Carmichael lambda function: Primary definition [online], functions.wolfram.com [dostęp 2017-10-13] .
↑ Carmichael lambda function: Zeros [online], functions.wolfram.com [dostęp 2017-10-13] .
1 2 PaulP. Erdős PaulP., CarlC. Pomerance CarlC., EricE. Schmutz EricE., Carmichael’s lambda function, „Acta Arithmetica”, 58 (4), 1991, s. 363–385, ISSN 0065-1036 [dostęp 2024-01-22] .
1 2 Carmichael lambda function: Specific values (subsection 03/01) [online], functions.wolfram.com [dostęp 2017-10-13] .

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.

Linki zewnętrzne

Carmichael function (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2025-04-23].

[1] Carmichael lambda function: Primary definition [online], functions.wolfram.com [dostęp 2017-10-13] .

[2] Carmichael lambda function: Zeros [online], functions.wolfram.com [dostęp 2017-10-13] .

[:1-3] 1 2 PaulP. Erdős PaulP., CarlC. Pomerance CarlC., EricE. Schmutz EricE., Carmichael’s lambda function, „Acta Arithmetica”, 58 (4), 1991, s. 363–385, ISSN 0065-1036 [dostęp 2024-01-22] .

[:0-4] 1 2 Carmichael lambda function: Specific values (subsection 03/01) [online], functions.wolfram.com [dostęp 2017-10-13] .