Carmichaels indikator

Den Carmichael indikator funktion , eller Carmichael indikator eller endda Carmichael funktion , bemærkede λ , defineres strengt positive naturlige tal; det associeres med et heltal n det mindste heltal m tilfredsstiller, for ethvert heltal en primtal med n , en m ≡ 1 mod n . Det blev introduceret af Robert Daniel Carmichael i en artikel fra 1910.

Carmichael indicatrix λ har et tæt forhold til Euler indicatrix- funktionen φ , især λ ( n ) deler φ ( n ) . De to funktioner falder sammen i 1, 2, 4, kræfterne for et ulige primtal og deres fordobling, men adskiller sig alle andre steder.

Definitioner og første egenskaber

Heltalene en prime med n er nøjagtigt dem, der er inverterbare modulo n (ved Bachet-Bézout-sætningen og dens omvendte). Så hvis to heltal m og k tilfredsstiller en m ≡ 1 mod n og en k ≡ 1 mod n , er også resten af ​​den euklidiske opdeling af den ene efter den anden. Definitionen kan derfor omformuleres:

• λ ( n ) er det unikke heltal således, at
  • for ethvert heltal en prime med n , en λ ( n ) ≡ 1 mod n
  • hvis for et hvilket som helst heltal en primær med n , en m mod 1 mod n , så deler λ ( n ) m .

Vi udleder derefter af Eulers sætning, at:

• λ ( n ) deler φ ( n ) .

Definitionen resulterer også af den kinesiske restsætning, at:

• hvis m og n er coprime, er λ ( m × n ) det mindst almindelige multiplum af λ ( m ) og λ ( n ) .

Definitionen kan omformuleres ved hjælp af gruppeteori . Et heltal et primtal med n er nøjagtigt et heltal, hvis klasse modulo n er et inverterbart element i ringen ℤ / n ℤ , det vil sige et element i den multiplikative gruppe (ℤ / n ℤ) *. Per definition kaldes det mindste heltal m, der tilfredsstiller α m = 1 for ethvert element α i en gruppe, eksponenten for denne gruppe og derfor:

• λ ( n ) er eksponenten for den multiplikative gruppe (ℤ / n ℤ) * af ringens invertible elementer ℤ / n ℤ .

En anden karakterisering af eksponenten giver

• λ ( n ) er det mindst almindelige multipel af rækkefølgen af ​​elementerne i (ℤ / n ℤ) *.

Vi finder således, at λ ( n ) deler φ ( n ), som er kardinalen eller rækkefølgen af ​​gruppen (ℤ / n ℤ) * og derfor et fælles multiplum af rækkefølgen af ​​dens elementer (ved Lagrange's sætning ).

I en endelig kommutativ gruppe , som (ℤ / n ℤ) *, findes der et element af orden eksponenten, det vil sige at:

• der findes et element af (ℤ / n ℤ) * af rækkefølgen λ ( n ) .

Vi udleder straks, at:

• λ ( n ) = φ ( n ) hvis og kun hvis gruppen (ℤ / n ℤ) * er en cyklisk gruppe .

Når p er prime, er ℤ / p ℤ et endeligt felt (prime), og dets multiplikative gruppe (ℤ / p ℤ) * er derefter cyklisk. Derfor :

• hvis p er primær, λ ( p ) = φ ( p ) = p - 1 .

Eksempler

Vi har ikke altid λ ( n ) = φ ( n )  : den multiplikative gruppe (ℤ / 8 ℤ) * er Klein-gruppen i rækkefølge 4 og eksponent 2, derfor har vi λ (8) = 2 men φ (8 ) = 4 .

Det er ikke kun de primtal, som funktionerne φ og λ har samme værdi for: vi kontrollerer, at (ℤ / 4 ℤ) * og (ℤ / 6 ℤ) * er af rækkefølge 2, derfor er λ (4) = φ ( 4) = 2 og λ (6) = φ (6) = 2 , (ℤ / 9 ℤ) * er af rækkefølge φ (9) = 6 , og 2 er et element i rækkefølge 6 af (ℤ / 9 ℤ) * derfor er λ (9) = φ (9) = 6 (de tilfælde, hvor φ ( n ) = λ ( n ) er specificeret i det følgende afsnit).

Følgende oeis: A002322 giver de første værdier af Carmichaels funktion λ (og foreslår andre i referencerne). De første 36 værdier for funktionen λ er angivet i nedenstående tabel med værdierne for det tilsvarende Euler- indeks φ .

ikke	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

Beregning af λ ( n )

Vi ved, hvordan man beregner λ ( m × n ), der kender λ ( m ) og λ ( n ), når m og n er coprime. Vi kan derfor beregne λ ( n ) fra nedbrydningen til primfaktorer for n , hvis vi ved, hvordan vi beregner λ ( p r ) for p et primtal, som vi opnår ved at studere de tilsvarende multiplikative grupper:

• hvis p er et ulige primtal og r ≥ 1 et heltal, så er den multiplikative gruppe (ℤ / p r ℤ) * den cykliske gruppe af rækkefølge φ ( p r ) = p r - p r - 1  ;
• hvis r ≥ 2, den multiplikative gruppe (ℤ / 2 r ℤ) *, er en gruppe af kardinal φ (2 r ) = 2 r - 1 , produkt af en gruppe af rækkefølge 2 og en cyklisk gruppe af rækkefølge 2 r - 2 , det vil sige, hvis r > 2, en gruppe af eksponent λ (2 r ) = 2 r - 2 , hvis r = 2 har gruppen kardinal og eksponent 2.

Vi får derefter en mere beregningsmæssig karakterisering af Carmichaels indikatorfunktion (undertiden taget til definition, især i den originale artikel af Carmichael).

Carmichaels sætning. - Carmichael-indikatorfunktionen er funktionen λ defineret på strengt positive heltal af:

• λ (1) = 1  ;
• λ ( p r ) = φ ( p r ) = p r - p r - 1 , for p prime ulige og r > 0 eller p = 2 og 0 < r ≤ 2;
• λ (2 r ) =1/2φ ( 2 r ) = 2 r - 2 , for r > 2;
• λ ( p 1 r 1 ... p k r k ) = ppcm (λ ( p 1 r 1 ), ..., λ ( p k r k )) , hvor p i er forskellige primtal.

Carmichaels indikatorfunktion tager den samme værdi som Eulers indikatorfunktion i n hvis og kun hvis gruppen (ℤ / n ℤ) * er cyklisk, dvs. hvis og kun hvis:

• n = 1  ;
• n = 2 eller n = 4  ;
• n = p r eller n = 2 p r , en ikke-nul-effekt ( r > 0) af et ulige primtal heltal p eller det dobbelte af en sådan styrke;

(følgende oeis: A034380 viser de første værdier for kvotientenφ ( n )/λ ( n )og tilbyder andre data som referencer).

Andre egenskaber

Vi udleder enten fra definitionen eller fra den mere eksplicitte form, som sætningen giver, at:

• hvis m kløfter n , derefter λ ( m ) kløfter Å ( n )  ;

i særdeleshed :

• hvis n er delelig med p prime, så er λ ( n ) delelig med p - 1  ;
• hvis n > 2 , så er λ ( n ) et lige antal (konsekvens af det foregående);
• hvis n er delelig med p 2, hvor p er primær, er λ ( n ) delelig med p .

Når n er et tal uden en kvadratfaktor, dvs. n er produktet af forskellige primtal p 1 , ..., p k  :

• λ ( p 1 ... p k ) = ppcm ( p 1 -1, ..., p k - 1)  ;
• for ethvert heltal a , a λ ( n ) + 1 ≡ a mod n .

Carmichael Numbers

De Carmichael tal er naturlige tal n , der ikke først , men som ikke desto mindre opfylder indgåelse af Fermats lille sætning , nemlig:

for ethvert heltal en prim med n , en n - 1 ≡ 1 mod n .

Carmichael studerer dem i den samme artikel, hvor han introducerer sin indikatorfunktion og især giver denne karakterisering, der følger straks af den definition, der er vedtaget ovenfor:

et tal n, som ikke er prime, er Carmichaels hvis og kun hvis λ ( n ) deler n - 1 .

Derfor :

• et Carmichael-tal er nødvendigvis ulige, fordi n - 1 kan deles med λ ( n ) lige (vi har n > 2 , og se forrige afsnit);
• et Carmichael-tal n er prime med λ ( n ) , derfor uden en kvadratfaktor (se forrige afsnit) eller produkt af alle forskellige primtal.

Ved at udnytte disse egenskaber og udtrykket i dette tilfælde af λ ( n ) (se forrige afsnit) bliver karakteriseringen af ​​Carmichael:

Sætning. - Et naturligt tal n, som ikke er prime, er et Carmichael-tal, hvis og kun hvis det er et produkt med forskellige ulige primtal, lad n = p 1 … p k , der tilfredsstiller p i - 1 deler n - 1 , for 1 ≤ i ≤ k .

Dette resultat, demonstreret i Carmichaels artikel, kaldes undertiden Korselts sætning (se den detaljerede artikel Carmichaels nummer ).

Noter og referencer

1. Demazure 2008 , s.  90.
2. Carmichael 1910 , s.  232.
3. Carmichael 1910 , s.  237.
4. Carmichael 1910 , s.  237-238.

Bibliografi

• (en) RD Carmichael , “  Note on a new number theory function  ” , Bulletin of the American Mathematical Society , bind.  16, nr .  5,1910, s.  232–238 ( DOI  10.1090 / s0002-9904-1910-01892-9 , læs online ) ;
• Michel Demazure , Algebra-kursus: Primality. Delbarhed. Koder. ,2008[ detalje af udgaven ] (s 90-94).
• (en) Hans Riesel , Prime Numbers and Computer Methods for Factorization (anden udgave) , Boston, Birkhäuser,1994, 464  s. ( ISBN  0-8176-3743-5 , læs online )