Carmichaelova funkce

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 1. ledna 2020; ověření vyžaduje 1 úpravu .

Carmichaelova funkce je číselně teoretická funkce , označovaná , rovna nejmenšímu exponentu tak, že $\lambda (n)$ $m$

a^{m}\equiv 1{\pmod {n))

pro všechna celá čísla coprime s modulo . V jazyce teorie grup je exponent skupiny multiplikativních zbytků modulo . $A$ $n$ $\lambda (n)$ $n$

Zde je tabulka prvních 36 hodnot funkční sekvence A002322 v OEIS v porovnání s hodnotami Eulerovy funkce . (různé hodnoty jsou zvýrazněny tučně) $\lambda (n)$ $\varphi$

n	jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct	16	17	osmnáct	19	dvacet	21	22	23	24	25	26	27	28	29	třicet	31	32	33	34	35	36
$\lambda (n)$	jeden	jeden	2	2	čtyři	2	6	2	6	čtyři	deset	2	12	6	čtyři	čtyři	16	6	osmnáct	čtyři	6	deset	22	2	dvacet	12	osmnáct	6	28	čtyři	třicet	osm	deset	16	12	6
$\varphi (n)$	jeden	jeden	2	2	čtyři	2	6	čtyři	6	čtyři	deset	čtyři	12	6	osm	osm	16	6	osmnáct	osm	12	deset	22	osm	dvacet	12	osmnáct	12	28	osm	třicet	16	dvacet	16	24	12

Příklad

1,3,5,7 jsou všechna čísla menší než 8 a relativně prvočísla, takže Carmichaelova funkce je 2. Eulerova funkce je 4, protože v seznamu 1,3,5,7 jsou právě 4 čísla. $1^{2}\equiv 1{\pmod {8));\ 3^{2}=9\equiv 1{\pmod {8));\ 5^{2}=25\equiv 1{ \pmod {8));\ 7^{2}=49\ekviv 1{\pmod {8}}$ $\lambda (8)$ $\varphi (8)$

Carmichaelova věta

Carmichaelova funkce mocnin lichých prvočísel, stejně jako pro čísla 2 a 4, je rovna Eulerově funkci ; pro mocniny dvou větší než 4 se rovná polovině Eulerovy funkce: $\lambda (n)$ $\varphi (n)$

\lambda (n)={\begin{cases}\;\;\varphi (n)&{\text{if ))n=2,3,4,5,6,7,9,10, 11,13,14,17,18,19,22,23,25,26,27,29\tečky \\{\frac {1}{2}}\varphi (n)&{\text{if }} n=8,16,32,64,128,256\tečky \end{cases}}

Eulerova funkce pro mocniny prvočísel je

\varphi (p^{k})=p^{k-1}(p-1).\;

Základní teorémem aritmetiky může být jakýkoli reprezentován jako $n>1$

n=p_{1}^{a_{1}}p_{2}^{a_{2}}\tečky p_{s}^{a_{s}}

kde jsou prvočísla a všechny . ${\displaystyle p_{1}<p_{2}<\tečky <p_{s))$ $a_{i}>0$

V obecném případě je nejmenší společný násobek všech přesných mocnin prvočísel zahrnutých do faktorizace: $\lambda (n)$ $\lambda (p_{i}^{a_{i)))$ $n$

\lambda (n)=\název operátora {lcm} [\lambda (p_{1}^{a_{1))),\;\lambda (p_{2}^{a_{2))),\ tečky ,\lambda (p_{s}^{a_{s}})].

Carmichaelova věta

Pokud coprime, tak $a,n$

a^{\lambda (n)}\equiv 1{\pmod {n))

Jinými slovy, Carmichaelův teorém říká, že funkce definovaná výše uvedeným vzorcem skutečně splňuje definici Carmichaelovy funkce. Tuto větu lze dokázat pomocí primitivních kořenů a čínské věty o zbytku .

Důkaz

Nejprve dokažme, že pro všechna koprimá c , . $A$ $n$ $a^{\lambda (n)}\equiv 1{\pmod {n))$

Podle Fermatova malého teorému pro jakýkoli jednoduchý modul a jakýkoli koprime modul máme . $p$ $A$ $a^{p-1}=1+hp$

Pokud , pak ${\displaystyle a^{p^{k-1}(p-1)}=1+hp^{k))$

$a^{p^{k}(p-1)}=(1+hp^{k})^{p}=1+h^{p}pp^{k}+\tečky =1+ h_{0}p^{k+1}$

Pak metodou matematické indukce dostaneme, že pro všechny . $A$ ${\displaystyle a^{p^{k-1}(p-1)}=a^{\lambda (p^{k})}\equiv 1{\pmod {p^{k))))$

Pro modul 2 je vztah poněkud silnější:

Pokud je to liché, tak . $A$ $a=1+2h$

Pak . ${\displaystyle a^{2}=1+4h(h+1)=1+8C_{h+1}^{2))$

Dále, pokud , tak $a^{2^{k-2}}=1+2^{k}h$

$a^{2^{k-1}}=(1+2^{k}h)^{2}=1+2^{k+1}(h+2^{k-1}h ^{2})$

Potom matematickou indukcí získáme, že pro všechny liché pro , platí, že . $A$ $k\geqslant 3$ ${\displaystyle a^{2^{k-2}}=a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k))))$

Konečně, jestliže a je společné s , pak a , tak a a pak . $n=2^{k}p_{1}^{a_{1}}\tečky p_{s}^{a_{s}}$ $A$ $n$ $a^{\lambda (p_{j}^{a_{j)))}\equiv 1{\pmod {p_{j}^{a_{j))))$ ${\displaystyle a^{\lambda (2^{k})}\equiv 1{\pmod {2^{k))))$ $a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{a_{j))))$ ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {2^{k))))$ $a^{\lambda (n)}\equiv 1{\pmod {n))$

Všimněte si také, že u žádného tvrzení nelze posílit: exponent je minimum, pro které . To lze snadno dokázat rozporem. $A$ $\lambda (n)$ $a^{\lambda (n)}\equiv 1{\pmod {n))$

Vskutku, budiž prvočíslo takové, že pro všechny . Od , pak rozděluje některé , tedy pro všechny . To však odporuje skutečnosti, že grupa je cyklická v , a v , je v rozporu s tím, že grupa má exponent . ■ $q$ $A$ $a^{\lambda (n)/q}\equiv 1{\pmod {n))$ $\lambda (n)=\název operátora {lcm} [\lambda (p_{1}^{a_{1))),\;\lambda (p_{2}^{a_{2))),\ tečky ,\lambda (p_{s}^{a_{s}})].$ $q$ $\lambda (p_{i}^{a_{i)))$ $A$ $a^{\lambda (p_{i}^{a_{i)))/q}\equiv 1{\pmod {p_{i}^{a_{i))))$ $\mathbb {Z} _{p^{k}}^{\times }$ $p>2$ $p=2$ $\mathbb {Z} _{2^{k}}^{\times }$ $2^{k-2}$

Souvislost mezi Carmichaelovou, Eulerovou a Fermatovou větou

Protože Carmichaelova funkce rozděluje Eulerovu funkci (posloupnost kvocientů, viz OEIS sekvenci A034380 ), je Carmichaelova věta silnějším výsledkem než klasická Eulerova věta . Je jasné, že Carmichaelova věta souvisí s Eulerovou větou , protože exponent konečné Abelovské grupy vždy rozděluje řád grupy. Carmichaelovy a Eulerovy funkce se liší i pro malé argumenty: , ale liší se vždy, když skupina zbytků modulo nemá generátor (viz sekvence A033949 ). $\lambda (n)$ $\varphi (n)$ $\lambda (15)=4$ $\varphi (15)=8$ $n$

Fermatova malá věta je speciální případ Eulerovy věty, ve které je modul prvočíslo. Carmichaelův teorém pro moduly prvočísel dává stejné tvrzení, protože skupina zbytků modulo prime je cyklická , to znamená, že její řád a exponent jsou stejné. $n$

Vlastnosti Carmichaelovy funkce

Dělitelnost

a|b\Rightarrow \lambda (a)|\lambda (b)

Funkce Carmichael z NOC

Pro jakákoli přirozená čísla platí, že $a,b$

\lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))

To bezprostředně vyplývá z definice Carmichaelovy funkce.

Primitivní kořeny jednoty

Jestliže a jsou coprime a jsou modulo exponenty , pak $a,n$ $m$ $A$ $n$

m|\lambda (n)

Jinými slovy, řád primitivního kořene jednoty ve zbytku kruhu modulo dělí . V rámci teorie grup je toto tvrzení prostým důsledkem definice exponentu grupy. $n$ $\lambda (n)$

Délka cyklu exponentu

Jestliže for označuje největší index prvočísel v kanonickém rozkladu , pak pro všechny (včetně ne coprime s ) a all , $n$ ${\displaystyle x_{\max ))$ $n$ $A$ $n$ ${\displaystyle k\geqslant x_{\max ))$

a^{k}\equiv a^{k+\lambda (n)}{\pmod {n))

Zejména pro čtverec bez (pro to ), pro všechny $n$ $n$ $x_{\max }=1$ $A$

a\equiv a^{\lambda (n)+1}{\pmod {n))

Průměrné a typické hodnoty

Pro jakékoli a konstantní : $x>16$ $B$

{\displaystyle {\frac {1}{x}}\sum \limits _{n\leq x}\lambda (n)={\frac {x}{\ln x}}e^{B(1+o (1))\ln \ln x/(\ln \ln \ln x)))

[1] [2] .

Tady

B=e^{-\gamma }\prod _{p}\left({1-{\frac {1}{(p-1)^{2}(p+1)))}\vpravo )\cca 0,34537\ .

Pro všechny , kromě čísel, platí, že: $N$ $n\leqslant N$ $o(N)$

{\displaystyle \lambda (n)=n/(\ln n)^{\ln \ln \ln n+A+o(1)))

kde je konstanta [2] [3] , $A$

A=-1+\sum \limits _{p}{\frac {\ln p}{(p-1)^{2}}}\cca 0,2269688\ .

Dolní hranice

Pro dostatečně velké a pro všechny existuje alespoň $N$ $\Delta \geq \ln ^{3}\ln N$

{\displaystyle Ne^{-0.69{\sqrt[{3}]{\Delta \ln \Delta ))))

přirozená čísla taková, že [4] . $n\leq N$ ${\displaystyle \lambda (n)\leqslant ne^{-\Delta ))$

Pro jakoukoli posloupnost přirozených čísel , jakoukoli konstantu a pro dostatečně velké : $n_{1}<n_{2}<n_{3}<\cdots$ $0<c<1/\ln 2$ $i$

\lambda (n_{i})>(\ln n_{i})^{c\ln \ln \ln n_{i))

[5] [6] .

Malé hodnoty

Pro konstantu a dostatečně velký klad existuje celé číslo takové, že [6] . Navíc to tak vypadá $C$ $A$ $n>A$ $\lambda (n)<(\ln A)^{c\ln \ln \ln A}$ $n$

n=\prod \limits _{(q-1)|m,\ q{\text{ je prvočíslo))}q

pro některé bez čtverců [5] . $m<(\ln A)^{c\ln \ln \ln A}$

Sada hodnot funkce Carmichael

Soubor hodnot Carmichaelovy funkce nepřesahující má mohutnost $X$

{\frac {x}{\ln ^{\eta +o(1)}x}}\ ,

kde [7] $\eta =1-(1+\ln \ln 2)/\ln 2=0,08607\tečky$

Viz také

Poznámky

↑ Věta 3 v Erdosu (1991)
↑ 1 2 Sandor & Crstici (2004) s. 194
↑ Věta 2 v Erdosu (1991)
↑ Věta 5 ve Friedlanderu (2001)
↑ 1 2 Věta 1 v Erdosu 1991
↑ 1 2 Sandor & Crstici (2004) s.193
↑ Ford, Kevin; Luca, Florian & Pomerance, Carl (27. srpna 2014), Obraz Carmichaelovy ?-funkce, arΧiv : 1408.6506 [math.NT].

Literatura

Bukhshtab A. A. Teorie čísel. - M .: Vzdělávání, 1966. (kap. 11 s. 2)
Erdos, Paule; Pomerance, Carle; Schmutz, Erik. Carmichaelova lambda funkce (neopr.) // Acta Arithmetica. - 1991. - T. 58 . - S. 363-385 . — ISSN 0065-1036 .
Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. Období generátoru energie a malé hodnoty Carmichaelovy funkce // Matematika výpočtu : deník. - 2001. - Sv. 70 . - S. 1591-1605, 1803-1806 . — ISSN 0025-5718 . - doi : 10.1090/s0025-5718-00-01282-5 .
Šándor, Jozsef; Crstici, Bořislav. Příručka teorie čísel II (neopr.) . - Dordrecht: Kluwer Academic , 2004. - S. 32-36,193-195. — ISBN 1-4020-2546-7 .
Carmichael, R. D. Teorie čísel (neurčeno) . — Nabu Press. — ISBN 1144400341 .