Carmichael funktion

Carmichael

λ

-funktion:

λ (n)

för

1 \leq n \leq 1000

(jämfört med Euler

φ

-funktion)

I talteorin , en gren av matematiken , är Carmichael -funktionen $λ (n)$ av ett positivt heltal $n$ det minsta positiva heltal $m$ så att

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

håller för varje heltal $ett$ coprime till $n$ . I algebraiska termer är $λ (n)$ exponenten för den multiplikativa gruppen av heltal modulo $n$ .

Carmichael-funktionen är uppkallad efter den amerikanske matematikern Robert Carmichael som definierade den 1910. Den är också känd som Carmichaels λ-funktion, den reducerade totientfunktionen och den minst universella exponentfunktionen .

Följande tabell jämför de första 36 värdena på $λ (n)$ (sekvens A002322 i OEIS ) med Eulers totientfunktion $φ$ (i fetstil om de är olika; $n$ s så att de är olika listas i OEIS : A033949 ).

$n$	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	26	27	28	29	30	31	32	33	34	35	36
$λ (n)$	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	12	18	6	28	4	30	8	10	16	12	6
$φ (n)$	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12

Numeriska exempel

Carmichaels funktion vid 5 är 4, $λ (5) = 4$ , eftersom för alla tal $0<a<5$ prime till 5, dvs ${\ displaystyle a\i \{1,2,3,4\}~,}$ det finns $a^{m}\equiv 1\,({\text{mod }}5 )$ med $m=4,$ nämligen $1 1\cdot4 = 1 4 \equiv 1 (mod 5)$ , $24 = 16 \equiv 1 (mod 5)$ , $34 = 81 \equiv 1 (mod 5)$ och $. 42\cdot2 = 162 \equiv 12 (mod 5$ ) Och denna $m = 4$ är den minsta exponenten med denna egenskap, eftersom $2^{2}=4\not \equiv 1\,({\text{mod }}5 )$ (och $3^{2}=9\not \equiv 1\,({\text{mod }}5)$ också.) Dessutom Eulers totient funktion vid 5 är 4, $φ (5) = 4$ , eftersom det finns exakt 4 tal mindre än och coprime till 5 (1, 2, 3 och 4). Eulers teorem försäkrar att $a 4 \equiv 1 (mod 5)$ för alla $en$ coprime till 5, och 4 är den minsta exponenten.
Carmichaels funktion vid 8 är 2, $λ (8) = 2$ , eftersom för vilket tal som helst $ett$ primtal till 8, dvs $a\in \{1,3,5, 7\}~,$ gäller att $a 2 \equiv 1 (mod 8)$ . Nämligen $1 1\cdot2 = 1 2 \equiv 1 (mod 8)$ , $32 = 9 \equiv 1 (mod 8)$ , $52 = 25 \equiv 1 (mod 8)$ och $72 = 49 \equiv 1 (mod 8)$ . Eulers totientfunktion vid 8 är 4, $φ (8) = 4$ , eftersom det finns exakt 4 tal mindre än och coprime till 8 (1, 3, 5 och 7). Dessutom säkerställer Eulers teorem att $a 4 \equiv 1 (mod 8)$ för alla $en$ coprime till 8, men 4 är inte den minsta exponenten.

Beräknar $λ (n)$ med Carmichaels sats

Genom den unika faktoriseringssatsen kan vilken som helst $n > 1$ skrivas på ett unikt sätt som

n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{ r_{k}}

där $p 1 < p 2 < ... < p k$ är primtal och $r 1, r 2, ..., r k$ är positiva heltal. Då är $λ (n) den$ minsta gemensamma multipeln av $λ$ för var och en av dess primtalsfaktorer:

\lambda (n)=\operatörsnamn {lcm} {\Bigl (}\lambda \left(p_{1}^{r_{1}}\right),\lambda \left(p_{2}^{ r_{2}}\right),\ldots ,\lambda \left(p_{k}^{r_{k}}\right){\Bigr )}.

Detta kan bevisas med hjälp av den kinesiska restsatsen .

Carmichaels sats förklarar hur man beräknar $λ$ av en primtalspotens $p r$ : för en potens av ett udda primtal och för 2 och 4 är $λ (p r)$ lika med Euler totienten $φ (p r)$ ; för potenser av 2 större än 4 är det lika med hälften av Euler-toienten:

\lambda (p^{r}) ={\begin{cases}{\tfrac {1}{2}}\varphi \left(p^{r}\right)&{\text{if }}p=2\land r\geq 3\;( {\mbox{ie }}p^{r}=8,16,32,64,128,256,\dots )\\\varphi \left(p^{r}\right)&{\mbox{annars}}\;( {\mbox{ie }}p^{r}=2,4,3^{r},5^{r},7^{r},11^{r},13^{r},17^{ r},19^{r},23^{r},29^{r},31^{r},\dots )\end{case}}

Eulers funktion för primpotenser $p r$ ges av

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

Egenskaper för Carmichael-funktionen

I det här avsnittet är ett heltal $n$ delbart med ett heltal som inte är noll $m$ om det finns ett heltal $k$ så att $n=km$ . Detta skrivs som

m\mid n.

Ordningsföljd av element modulo $n$

Låt $a$ och $n$ vara coprime och låt $m$ vara den minsta exponenten med $a m \equiv 1 (mod n)$ , då gäller det att

m\,|\,\lambda (n)

.

Det vill säga ordningen m $:= ord n (a)$ av en enhet $a$ i ringen av heltal modulo $n$ delar $λ (n)$ och

\lambda (n)=\max\{\operatörsnamn {ord} _{n}(a)\, \colon \,\gcd(a,n)=1\}

Minimalitet

Antag att $a m \equiv 1 (mod n)$ för alla tal $ett$ primtal med $n$ . Sedan $λ (n) | m$ .

Bevis: Om $m = kλ (n) + r$ med $0 \leq r < λ (n)$ , då

a^{r}=1^{ k}\cdot a^{r}\equiv \left(a^{\lambda (n)}\right)^{k}\cdot a^{r}=a^{k\lambda (n)+r} =a^{m}\ekvivalent 1{\pmod {n}}

för alla tal $ett$ primtal med $n$ . Det följer $r = 0$ , eftersom $r < λ (n)$ och $λ (n)$ det minimala positiva talet.

$λ (n)$ delar $φ (n)$

Detta följer av elementär gruppteori , eftersom exponenten för en ändlig grupp måste dela upp gruppens ordning. $λ (n)$ är exponenten för den multiplikativa gruppen av heltal modulo $n$ medan $φ (n)$ är ordningen för den gruppen. I synnerhet måste de två vara lika i de fall där den multiplikativa gruppen är cyklisk på grund av förekomsten av en primitiv rot , vilket är fallet för udda primpotenser.

Vi kan alltså se Carmichaels sats som en skärpning av Eulers sats .

Delbarhet

a\,|\,b\Högerpil \lambda (a)\,|\,\lambda (b)

Bevis.

Per definition, för vilket heltal ${\displaystyle k} som helst$ , har vi att ${\displaystyle b\,|\,(k^{\lambda (b)}-1)} ,$ och därför $a\,|\,(k^{\lambda (b)}-1)$ . Med minimalitetsegenskapen ovan har vi $\lambda (a)\,|\,\lambda (b)$ .

Sammansättning

För alla positiva heltal $a$ och $b$ gäller det

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

.

Detta är en omedelbar konsekvens av den rekursiva definitionen av Carmichael-funktionen.

Exponentiell cykellängd

Om $är {\displaystyle r_{\mathrm {max} }=\max _{i}\{r_{i}\}}$ den största exponenten i primtalsfaktoriseringen $n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k }}$ av $n$ , sedan för alla $a$ (inklusive de som inte samprimeras till $n$ ) och alla $r \geq r max$ ,

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

I synnerhet för kvadratfritt $n$ ( $r max = 1$ ), för alla $a$ vi har

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

Förlängning för två potenser

För $ett$ coprime till (potenser av) 2 har vi $a = 1 + 2 h$ för vissa $h$ . Sedan,

a^{2}=1+4h(h+1)=1+8C

där vi drar fördel av att $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} C := ( h + 1) h / 2$ är ett heltal.

Så för $k = 3$ är $h$ ett heltal:

{\begin{aligned }a^{2^{k-2}}&=1+2^{k}h\\a^{2^{k-1}}&=\left(1+2^{k}h\right )^{2}=1+2^{k+1}\left(h+2^{k-1}h^{2}\right)\end{aligned}}

Genom induktion, när $k \geq 3$ , har vi

a^{2^{k-2}}\equiv 1{\pmod {2^{k}}}.

Den ger att $λ (2 k)$ är högst $2 k - 2$ .

Genomsnittligt värde

För alla $n \geq 16$ :

{\display}{\frac {1 n}}\summa _{i\leq n}\lambda (i)={\frac {n}{\ln n}}e^{B(1+o(1))\ln \ln n/(\ ln \ln \ln n)}}

(kallas Erdős approximation i det följande) med konstanten

B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0,34537

och $γ \approx 0,57721$ , Euler-Mascheroni-konstanten .

Följande tabell ger en översikt över de första $226 - 1 = 67108863$ värdena för $λ-$ funktionen, för båda, det exakta medelvärdet och dess Erdős-approximation.

Dessutom ges en översikt över de mer lättillgängliga "logaritm över logaritm"-värdena $LoL(n) := ln λ (n) / ln n$ med

$LoL n) 4/5 >_4/5 . > \Leftrightarrow λ (n) n$ (

Där, tabellposten i rad nummer 26 vid kolumn

$% LoL > 4/5 60,49$ →

indikerar att 60,49 % (≈ 40 000 000 ) av heltalen $1 \leq n \leq 67108863$ har $λ (n) > n 4 / 5$ vilket betyder att majoriteten av $λ-$ värdena är exponentiella i längden $l : n = log 2 ( )$ av ingången $n$ , nämligen

\left(2^{\frac {4}{5}}\right)^{l}=2^{\frac {4l}{5}}=\left(2^{l}\right) ^{\frac {4}{5}}=n^{\frac {4}{5}}.

$ν$	$n = 2 ν - 1$	summa $\sum _{i\leq n}\lambda (i)$	genomsnitt ${\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)$	Erdős genomsnitt	Erdős / exakt genomsnitt	$LoL$ genomsnitt	% $LoL$ > 4/5 _ _	% $LoL$ > 7/8 _ _
5	31	270	8,709677	68,643	7,8813	0,678244	41,94	35,48
6	63	964	15.301587	61,414	4,0136	0,699891	38,10	30.16
7	127	3574	28.141732	86,605	3,0774	0,717291	38,58	27,56
8	255	12994	50,956863	138,190	2,7119	0,730331	38,82	23.53
9	511	48032	93,996086	233,149	2,4804	0,740498	40,90	25.05
10	1023	178816	174,795699	406,145	2,3235	0,748482	41,45	26,98
11	2047	662952	323.865169	722.526	2,2309	0,754886	42,84	27,70
12	4095	2490948	608.290110	1304.810	2,1450	0,761027	43,74	28.11
13	8191	9382764	1145.496765	2383,263	2,0806	0,766571	44,33	28,60
14	16383	35504586	2167.160227	4392.129	2,0267	0,771695	46,10	29,52
15	32767	134736824	4111.967040	8153.054	1,9828	0,776437	47,21	29.15
16	65535	513758796	7839.456718	15225,430	1,9422	0,781064	49,13	28.17
17	131071	1964413592	14987.400660	28576,970	1,9067	0,785401	50,43	29.55
18	262143	7529218208	28721.797680	53869,760	1,8756	0,789561	51,17	30,67
19	524287	28935644342	55190.466940	101930,9 00	1,8469	0,793536	52,62	31.45
20	1048575	111393101150	106232.8409 00	193507.1 00	1,8215	0,797351	53,74	31,83
21	2097151	429685077652	204889.9090 00	368427,6 00	1,7982	0,801018	54,97	32.18
22	4194303	1660388309120	395867.5158 00	703289,4 00	1,7766	0,804543	56,24	33,65
23	8388607	6425917227352	766029.1187 00	1345633 .000	1,7566	0,807936	57,19	34,32
24	16777215	24906872655990	1484565.386 000	2580070 000	1,7379	0,811204	58,49	34,43
25	33554431	96666595865430	2880889.140 000	4956372 .000	1,7204	0,814351	59,52	35,76
26	67108863	375619048086576	5597160.066 000	9537863 .000	1,7041	0,817384	60,49	36,73

Rådande intervall

För alla tal $N$ och alla utom $o (N)$ positiva heltal $n \leq N$ (en "rådande" majoritet):

\lambda (n)={\frac {n}{(\ln n)^{\ln \ln \ln n+A+o(1)}}}

med konstanten

A:=-1+\sum _{p\in \mathbb {P} }{\frac {\ln p }{(p-1)^{2}}}\approx 0,2269688

Nedre gränser

För vilket tillräckligt stort antal $N som helst$ och för varje $Δ \geq (ln ln N) 3$ finns det som mest

N\exp \left(-0.69(\Delta \ln \Delta )^{\frac {1}{3}}\right)

positiva heltal $n \leq N$ så att $λ (n) \leq ne -Δ$ .

Minimal beställning

För varje sekvens $n 1 < n 2 < n 3 < \dots$ av positiva heltal, vilken konstant $0 som helst < c < 1 / ln 2$ , och vilken som helst tillräckligt stor $i$ :

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

Små värden

För en konstant $c$ och ett tillräckligt stort positivt $A$ , finns det ett heltal $n > A$ så att

\lambda (n)<\left(\ln A\right)^{c\ln \ln \ln A}.

Dessutom är $n$ av formen

n=\mathop {\prod _{q\in \mathbb {P} }} _{(q-1)|m}q

för något kvadratfritt heltal $m < (ln A) c ln ln ln A$ .

Bild på funktionen

Uppsättningen värden för Carmichael-funktionen har en räknefunktion

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

var

\eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\approx 0,08607

Använd i kryptografi

Carmichael-funktionen är viktig i kryptografi på grund av dess användning i RSA-krypteringsalgoritmen .

Se även

Carmichael nummer

Anteckningar

^ Carmichael, Robert Daniel (1910). "Anmärkning om en ny talteoretisk funktion" . Bulletin från American Mathematical Society . 16 (5): 232–238. doi : 10.1090/S0002-9904-1910-01892-9 .
^ Carmichael, Robert Daniel. Talteorin . Nabu Press. ISBN 1144400341 . ^{[ sida behövs ]}
^ Sats 3 i Erdős (1991)
^ ^a ^b Sándor & Crstici (2004) s.194
^ Sats 2 i Erdős (1991) 3. Normal ordning. (s.365)
^ Sats 5 i Friedlander (2001)
^ ^a ^b Sats 1 i Erdős 1991
^ ^a ^b Sándor & Crstici (2004) s.193
^ Ford, Kevin; Luca, Florian; Pomerance, Carl (27 augusti 2014). "Bilden av Carmichaels λ -funktion". Algebra & Talteori . 8 (8): 2009–2026. arXiv : 1408.6506 . doi : 10.2140/ant.2014.8.2009 .

Erdős, Paul ; Pomerance, Carl ; Schmutz, Eric (1991). "Carmichaels lambdafunktion" . Acta Arithmetica . 58 (4): 363–385. doi : 10.4064/aa-58-4-363-385 . ISSN 0065-1036 . MR 1121092 . Zbl 0734.11047 .
Friedlander, John B. ; Pomerance, Carl; Shparlinski, Igor E. (2001). "Perioden för kraftgeneratorn och små värden för Carmichael-funktionen" . Beräkningsmatematik . 70 (236): 1591–1605, 1803–1806. doi : 10.1090/s0025-5718-00-01282-5 . ISSN 0025-5718 . MR 1836921 . Zbl 1029.11043 .
Sándor, Jozsef; Crstici, Borislav (2004). Handbok i talteori II . Dordrecht: Kluwer Academic. s. 32–36, 193–195. ISBN 978-1-4020-2546-4 . Zbl 1079.11001 .
Carmichael, RD (2004-10-10). Talteorin . Nabu Press. ISBN 978-1144400345 .

[1] Carmichael, Robert Daniel (1910). "Anmärkning om en ny talteoretisk funktion" . Bulletin från American Mathematical Society . 16 (5): 232–238. doi : 10.1090/S0002-9904-1910-01892-9 .

[car-2] Carmichael, Robert Daniel. Talteorin . Nabu Press. ISBN 1144400341 . ^{[ sida behövs ]}

[3] Sats 3 i Erdős (1991)

[HBII194-4] Sándor & Crstici (2004) s.194

[5] Sats 2 i Erdős (1991) 3. Normal ordning. (s.365)

[6] Sats 5 i Friedlander (2001)

[Theorem_1_in_Erdős_1991-7] Sats 1 i Erdős 1991

[HBII193-8] Sándor & Crstici (2004) s.193

[9] Ford, Kevin; Luca, Florian; Pomerance, Carl (27 augusti 2014). "Bilden av Carmichaels λ -funktion". Algebra & Talteori . 8 (8): 2009–2026. arXiv : 1408.6506 . doi : 10.2140/ant.2014.8.2009 .