La funzione indicatore di Carmichael , o indicatore di Carmichael o anche funzione di Carmichael , annotata λ , è definita su numeri naturali strettamente positivi; associa ad un intero n il più piccolo intero m che soddisfa, per ogni intero un numero primo con n , a m ≡ 1 mod n . È introdotto da Robert Daniel Carmichael in un articolo del 1910.
L'indicatrice di Carmichael λ ha una stretta relazione con la funzione indicatrice di Eulero φ , in particolare λ ( n ) divide φ ( n ) . Le due funzioni coincidono in 1, 2, 4, le potenze di un numero primo dispari e le loro doppie, ma differiscono ovunque.
Gli interi un primo con n sono esattamente quelli che sono invertibili modulo n (per il teorema di Bachet-Bézout e il suo contrario). Quindi se due interi m e k soddisfano a m ≡ 1 mod n e a k ≡ 1 mod n , anche il resto della divisione euclidea dell'uno per l'altro. La definizione può quindi essere riformulata:
Deduciamo quindi dal teorema di Eulero che:
La definizione risulta anche, dal teorema cinese dei resti, che:
La definizione può essere riformulata utilizzando la teoria dei gruppi . Un intero un primo con n è esattamente un intero la cui classe modulo n è un elemento invertibile dell'anello ℤ / n ℤ , cioè un elemento del gruppo moltiplicativo (ℤ / n ℤ) *. Per definizione, il più piccolo intero m che soddisfa α m = 1 per qualsiasi elemento α di un gruppo è chiamato esponente di questo gruppo, e quindi:
Un'altra caratterizzazione dell'esponente dà
Troviamo quindi che λ ( n ) divide φ ( n ) che è il cardinale, o ordine, del gruppo (ℤ / n ℤ) * e quindi un multiplo comune degli ordini dei suoi elementi (per il teorema di Lagrange ).
In un gruppo commutativo finito, come (ℤ / n ℤ) *, esiste un elemento di ordine esponente, vale a dire che:
Ne deduciamo subito che:
Quando p è primo, ℤ / p ℤ è un campo finito (primo) e il suo gruppo moltiplicativo (ℤ / p ℤ) * è quindi ciclico. Pertanto :
Non sempre abbiamo λ ( n ) = φ ( n ) : il gruppo moltiplicativo (ℤ / 8 ℤ) * è il gruppo di Klein , di ordine 4 ed esponente 2, abbiamo quindi λ (8) = 2 ma φ (8 ) = 4 .
Non sono solo i numeri primi per i quali le funzioni φ e λ assumono lo stesso valore: controlliamo che (ℤ / 4 ℤ) * e (ℤ / 6 ℤ) * sono di ordine 2, quindi λ (4) = φ ( 4) = 2 e λ (6) = φ (6) = 2 , (ℤ / 9 ℤ) * è di ordine φ (9) = 6 e 2 è un elemento di ordine 6 di (ℤ / 9 ℤ) * quindi λ (9) = φ (9) = 6 (i casi in cui φ ( n ) = λ ( n ) sono specificati nel paragrafo successivo).
Il seguente oeis: A002322 fornisce i primi valori della funzione λ di Carmichael (e ne propone altri nei riferimenti). I primi 36 valori della funzione λ sono riportati nella tabella sottostante, con quelli del corrispondente indice di Eulero φ .
| non | 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 |
Sappiamo calcolare λ ( m × n ) conoscendo λ ( m ) e λ ( n ) quando m e n sono coprimi. Possiamo quindi calcolare λ ( n ) dalla scomposizione in fattori primi di n , se sappiamo calcolare λ ( p r ) per p un numero primo, che otteniamo studiando i corrispondenti gruppi moltiplicativi:
Otteniamo quindi una caratterizzazione più computazionale della funzione indicatore di Carmichael (a volte presa per definizione, in particolare nell'articolo originale di Carmichael).
Teorema di Carmichael. - La funzione indicatore di Carmichael è la funzione λ definita su interi strettamente positivi da:
La funzione indicatore di Carmichael assume lo stesso valore della funzione indicatore di Eulero in n se e solo se il gruppo (ℤ / n ℤ) * è ciclico, cioè se e solo se:
(il seguente oeis: A034380 elenca i primi valori del quozienteφ ( n )λ ( n )e offre altri dati come riferimento).
Si deduce, sia dalla definizione, sia dalla forma più esplicita data dal teorema, che:
in particolare :
Quando n è un numero senza fattore quadrato, cioè n è il prodotto di numeri primi distinti p 1 , ..., p k :
I numeri di Carmichael sono numeri naturali n che non sono primi ma che tuttavia soddisfano la conclusione del piccolo teorema di Fermat , ovvero:
per ogni intero un numero primo con n , a n - 1 ≡ 1 mod n .Carmichael li studia nello stesso articolo dove introduce la sua funzione di indicatore e dà in particolare questa caratterizzazione, che segue immediatamente dalla definizione adottata sopra:
un numero n che non è primo è di Carmichael se e solo se λ ( n ) divide n - 1 .Perciò :
Sfruttando queste proprietà, e dell'espressione in questo caso di λ ( n ) (vedi paragrafo precedente), la caratterizzazione di Carmichael diventa:
Teorema: un numero naturale n che non è primo è un numero di Carmichael se e solo se è un prodotto di numeri primi dispari distinti, sia n = p 1 … p k , soddisfacendo p i - 1 divide n - 1 , per 1 ≤ io ≤ k .
Questo risultato, dimostrato nell'articolo di Carmichael, è talvolta chiamato teorema di Korselt (vedi l'articolo dettagliato Il numero di Carmichael ).