Indicatorul lui Carmichael

Funcția indicator Carmichael , sau indicator Carmichael sau chiar funcția Carmichael , notată $λ$ , este definită pe numere naturale strict pozitive; se asociază cu un întreg n cel mai mic întreg m care îndeplinește, pentru orice număr întreg un prim cu n , $a m \equiv 1 mod n$ . Este introdus de Robert Daniel Carmichael într-un articol din 1910.

Indicatorul lui Carmichael $λ$ are o relație strânsă cu funcția $indicatorului$ Euler $φ$ , în special $λ ( n )$ împarte $φ ( n )$ . Cele două funcții coincid în 1, 2, 4, puterile unui număr prim impar și dublele lor, dar diferă peste tot.

Definiții și primele proprietăți

Întregii un prim cu n sunt exact cei care sunt modul n inversabil (prin teorema Bachet-Bézout și invers). Deci, dacă două numere întregi m și k satisfac $un m \equiv 1 mod n$ și $un k \equiv 1 mod n$ , restul împărțirii euclidiene a unuia cu celălalt. Prin urmare, definiția poate fi reformulată:

λ ( n ) este întregul unic astfel încât
- pentru orice număr întreg un prim cu n , $a λ ( n ) \equiv 1 mod n$
- dacă pentru orice număr întreg un prim cu n , $a m \equiv 1 mod n$ , atunci $λ ( n )$ împarte $m$ .

Apoi deducem din teorema lui Euler că:

$λ ( n )$ împarte $φ ( n )$ .

Definiția rezultă, de asemenea, prin teorema restului chinez, că:

dacă m și n sunt coprimă, atunci $λ ( m \times n )$ este cel mai mic multiplu comun al lui $λ ( m )$ și $λ ( n )$ .

Definiția poate fi reformulată folosind teoria grupurilor . Un întreg un prim cu n este exact un număr întreg a cărui clasă modulo n este un element inversabil al inelului ℤ / n ℤ , adică un element al grupului multiplicativ (ℤ / n ℤ) *. Prin definiție, cel mai mic întreg m care îndeplinește $α m = 1$ pentru orice element α al unui grup se numește exponentul acestui grup și, prin urmare:

$λ ( n )$ este exponentul grupului multiplicativ (ℤ / n ℤ) * al elementelor inversabile ale inelului ℤ / n ℤ .

O altă caracterizare a exponentului dă

$λ ( n )$ este cel mai mic multiplu comun al ordinilor elementelor din (ℤ / n ℤ) *.

Astfel, constatăm că $λ ( n )$ împarte $φ ( n )$ care este cardinalul sau ordinea grupului (ℤ / n ℤ) * și, prin urmare, un multiplu comun al ordinilor elementelor sale (prin teorema lui Lagrange ).

Într-un grup comutativ finit, cum ar fi (ℤ / n ℤ) *, există un element de ordine exponent, adică:

există un element de (ℤ / n ℤ) * de ordinul $λ ( n )$ .

Deducem imediat că:

$λ ( n ) = φ ( n )$ dacă și numai dacă grupul (ℤ / n ℤ) * este un grup ciclic .

Când p este prim, ℤ / p ℤ este un câmp finit (prim), iar grupul său multiplicativ (ℤ / p ℤ) * este apoi ciclic. Prin urmare:

dacă p este prim, $λ ( p ) = φ ( p ) = p - 1$ .

Exemple

Nu avem întotdeauna $λ ( n ) = φ ( n )$ : grupul multiplicativ (ℤ / 8 ℤ) * este grupul Klein , de ordinul 4 și exponentul 2, avem deci $λ (8) = 2$ dar $φ (8 ) = 4$ .

Nu numai numerele prime pentru care funcțiile φ și λ iau aceeași valoare: verificăm dacă (ℤ / 4 ℤ) * și (ℤ / 6 ℤ) * sunt de ordinul 2, deci $λ (4) = φ ( 4) = 2$ și $λ (6) = φ (6) = 2$ , (ℤ / 9 ℤ) * este de ordinul $φ (9) = 6$ , iar 2 este un element de ordinul 6 din (ℤ / 9 ℤ) * de aceea $λ (9) = φ (9) = 6$ (cazurile în care $φ ( n ) = λ ( n )$ sunt specificate în paragraful următor).

Următorul oeis: A002322 oferă primele valori ale funcției λ a lui Carmichael (și propune altele în referințe). Primele 36 de valori ale funcției $λ$ sunt date în tabelul de mai jos, cu cele ale $indicelui$ Euler corespunzător $φ$ .

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

Calculul lui λ ( n )

Știm cum să calculăm $λ ( m \times n )$ știind $λ ( m )$ și $λ ( n )$ când m și n sunt coprimă. Prin urmare, putem calcula $λ ( n )$ din descompunerea în factori primi ai lui n , dacă știm cum să calculăm $λ ( p r )$ pentru p un număr prim, pe care îl obținem prin studierea grupelor multiplicative corespunzătoare:

dacă p este un număr prim impar și r ≥ 1 un număr întreg, atunci grupul multiplicativ (ℤ / p r ℤ) * este grupul ciclic de ordinul $φ ( p r ) = p r - p r - 1$ ;
dacă r ≥ 2, grupul multiplicativ (ℤ / 2 r ℤ) *, este un grup de cardinale $φ (2 r ) = 2 r - 1$ , produs al unui grup de ordinul 2 și al unui grup ciclic de ordinul 2 r - 2 , adică, dacă r > 2, un grup de exponent $λ (2 r ) = 2 r - 2$ , dacă r = 2 grupul are cardinal și exponent 2.

Apoi obținem o caracterizare mai mult calculală a funcției indicator a lui Carmichael (uneori luată pentru definire, în special în articolul original al lui Carmichael).

Teorema lui Carmichael. - Funcția indicator a lui Carmichael este funcția $λ$ definită pe numere întregi strict pozitive prin:

$λ (1) = 1$ ;
$λ ( p r ) = φ ( p r ) = p r - p r - 1$ , pentru p prime impare și r > 0, sau p = 2 și 0 < r ≤ 2;
$λ (2 r ) = 1 / 2 φ ( 2 r ) = 2 r - 2$ , pentru r > 2;
$λ ( p 1 r 1 ... p k r k )$ = $ppcm (λ ( p 1 r 1 ), ..., λ ( p k r k ))$ , unde $p i$ sunt numere prime distincte.

Funcția indicator a lui Carmichael ia aceeași valoare ca funcția indicator Euler în $n$ dacă și numai dacă grupul (ℤ / n ℤ) * este ciclic, adică dacă și numai dacă:

$n = 1$ ;
$n = 2$ sau $n = 4$ ;
$n = p r$ sau $n = 2 p r$ , o putere diferită de zero ( r > 0) a unui număr întreg impare p sau dublul unei astfel de puteri;

(următorul oeis: A034380 listează primele valori ale coeficientului $φ ( n ) / λ ( n )$ , și oferă alte date ca referințe).

Alte proprietăți

Deducem, fie din definiție, fie din forma mai explicită dată de teoremă, că:

dacă $m$ împarte $n$ , atunci $λ ( m )$ împarte $λ ( n )$ ;

în special :

dacă $n$ este divizibil cu $p$ prim, atunci $λ ( n )$ este divizibil cu $p - 1$ ;
dacă $n > 2$ , atunci $λ ( n )$ este un număr par (consecință a celui precedent);
dacă $n$ este divizibil cu $p 2$ unde $p$ este prim, atunci $λ ( n )$ este divizibil cu $p$ .

Când $n$ este un număr fără factor pătrat, adică $n$ este produsul numerelor prime distincte $p 1 , ..., p k$ :

$λ ( p 1 ... p k ) = ppcm ( p 1 -1, ..., p k - 1)$ ;
pentru orice număr întreg $a$ , $a λ ( n ) + 1 \equiv a mod n$ .

Numerele lui Carmichael

Cele Numerele Carmichael sunt numere naturale $n$ care nu sunt în primul rând , dar care satisfac toate acestea , concluzia teoremei lui Fermat mic , și anume:

pentru orice număr întreg

un

prim cu n ,

a n - 1 \equiv 1 mod n

Carmichael le studiază în același articol în care își introduce funcția de indicator și dă în special această caracterizare, care rezultă imediat din definiția adoptată mai sus:

un număr

n

care nu este prim este al lui Carmichael dacă și numai dacă

λ ( n )

împarte

n - 1

Prin urmare:

un număr Carmichael este neapărat impar, deoarece $n - 1$ este divizibil cu $λ ( n ) pare$ (avem $n > 2$ și vedem secțiunea anterioară);
un număr Carmichael $n$ este prim cu $λ ( n )$ , deci fără un factor pătrat (vezi secțiunea anterioară), sau produs al tuturor numerelor prime distincte.

Profitând de aceste proprietăți și de expresia în acest caz a lui $λ ( n )$ (vezi secțiunea anterioară), caracterizarea lui Carmichael devine:

Teorema.— Un număr natural $n$ care nu este prim este un număr Carmichael dacă și numai dacă este un produs de numere prime impare distincte, fie $n = p 1 ... p k$ , satisfăcând $p i - 1$ împarte $n - 1$ , pentru $1 \leq i \leq k$ .

Acest rezultat, demonstrat în articolul lui Carmichael, este uneori numit teorema lui Korselt (vezi articolul detaliat numărul lui Carmichael ).

Note și referințe

Demazure 2008 , p. 90.
Carmichael 1910 , p. 232.
Carmichael 1910 , p. 237.
Carmichael 1910 , p. 237-238.

Bibliografie

(ro) RD Carmichael , „ Notă asupra unei noi funcții a teoriei numerelor ” , Buletinul Societății Americane de Matematică , vol. 16, nr . 5,1910, p. 232–238 ( DOI 10.1090 / s0002-9904-1910-01892-9 , citiți online ) ;
Michel Demazure , Curs de algebră: Primalitate. Divizibilitate. Coduri. ,2008[ detaliul ediției ] (pag. 90-94).
(ro) Hans Riesel , Prime Numbers and Computer Methods for Factorization (ediția a doua) , Boston, Birkhäuser,1994, 464 p. ( ISBN 0-8176-3743-5 , citit online )