Funkcja Carmichaela

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Funkcje matematyczne

dziedzina

Funkcje elementarne

Funkcje algebraiczne:

wymierna - niewymierna
wielomian
stała - liniowa - kwadratowa
homograficzna

Funkcje przestępne:

trygonometryczne - cyklometryczne
hiperboliczne - area
wykładnicza - logarytmiczna
potęgowa

Funkcje specjalne

błędu Γ Β (beta) η W Lamberta Bessela ζ

Funkcje teorioliczbowe

Möbiusa φ π λ

Własności

przebieg zmienności - parzystość - monotoniczność - ograniczoność - okresowość - różnowartościowość - suriektywność - wzajemna jednoznaczność - ciągłość

Funkcja λ Carmichaëla – funkcja określona dla dodatnich liczb całkowitych, której wartością dla danej liczby n jest najmniejsza liczba, taka, że liczba względnie pierwsza z n podniesiona do potęgi przystaje do 1 mod n.

$\bigwedge_{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.

Spis treści

1 Definicja Formalna
2 Własności
3 Twierdzenie Carmichaëla - związek funkcji z Małym Twierdzeniem Fermata
4 Przykład zastosowania funkcji Carmichaëla
5 Funkcja Carmichaëla i funkcja Eulera
6 Wartości dla 25 początkowych liczb naturalnych
7 Wartości dla 7 najmniejszych liczb Carmichaëla
8 Zobacz również
9 Bibliografia

[edytuj] Definicja Formalna

Ścisła definicja funkcji Carmichaëla jest taka, że dla danej liczby n, λ(n) to 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:

$\forall_{x \in Z_n^*}\ x^k \equiv 1 \Rightarrow k \geq \lambda(n)$

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

[edytuj] Własności

Poniżej λ-oznacza funkcję Carmichaёla, φ-funkcję Eulera.

[edytuj] Ś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):

$\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_n^{\alpha_n})\big) & n=\prod_{i=1}^{k}p_i^{\alpha_i} \end{matrix} \right.$

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

[edytuj] Oszacowania

Dla dowolnej liczby naturalnej k zachodzi oszacowanie górne:

$\lambda(k) \leq \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}$

[edytuj] Wartość dla liczb pierwszych

Jeżeli p - liczba pierwsza to zachodzi:

$λ(p) = φ(p) = p - 1$

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

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

$λ(p) = p k - 1 (p - 1) = φ(p)$

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

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

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

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

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

[edytuj] Przykład zastosowania funkcji Carmichaëla

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))=2*30=60. Tak więc - $3^{60}\ mod\ 248=1$ . Co więcej - ponieważ 60 "mieści się" w 2000 dokładnie 33 razy to zachodzi:

$3^{2000}\ mod\ 248=((3^{60})^{33})(3^{20})\ mod\ 248=(1^{33})(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 = 25^2\ mod\ 248 = 625\ mod\ 248=129$

[edytuj] Funkcja Carmichaëla i funkcja Eulera

Ponieważ patrząc w odpowiedni sposób na funkcję Eulera, obie w/w 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.

[edytuj] 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

Wykres funkcji dla przedziału <1;23>

[edytuj] Wartości dla 7 najmniejszych liczb Carmichaëla

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

[edytuj] Zobacz również

[edytuj] Bibliografia

[1] Paul Erdős, Carl Pomerance, Eric Schmutz, Carmichael's lambda function, Acta Arithmetica, vol. 58, 363--385, 1991

[2] 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, pp. 1591-1605, 2001

Źródło: "http://pl.wikipedia.org../../../f/u/n/Funkcja_Carmichaela_c628.html"

Kategoria: Teoria liczb