Teorema di Korselt
Un numero composto \( n \) è un numero di Carmichael se e solo se soddisfa le seguenti tre condizioni:
- \( n \) è senza quadrati, cioè non esiste un primo \( p \) tale che \( p^2 \) divide \( n \).
- \( n \) è il prodotto di almeno tre numeri primi distinti, ossia può essere scritto come \( n = p_1 p_2 \dots p_k \) con \( k \geq 2 \).
- Per ogni numero primo \( p_i \) che divide \( n \), si ha: \[ p_i - 1 \mid n - 1 \] ossia \( p_i - 1 \) divide \( n - 1 \).
Il teorema di Korselt è un metodo per verificare se un numero è di Carmichael, senza dover controllare la condizione di Fermat per ogni base \( a \).
I numeri di Carmichael sono quei numeri composti \( n \) che soddisfano la condizione di Fermat per tutti i numeri primi \( a \) coprimi con \( n \), ovvero:
\[ a^{n-1} \equiv 1 \pmod{n} \]
In particolar modo la terza condizione del teorema implica che tutti i primi divisori di \( n \) devono essere congruenti a 1 modulo un divisore comune di \( n - 1 \).
Esempio
Il più piccolo numero di Carmichael è 561 che soddisfa tutte e tre le condizioni di Konselt.
- E' privo di quadrati perché 561 = 3 × 11 × 17 e nessuno dei fattori primi è al quadrato.
- Il numero 561 è il prodotto di almeno tre primi distinti
- Ogni fattore primo (p-1) divide (n-1)=560
- 2 (cioè 3 - 1) divide 560
- 10 (cioè 11 - 1) divide 560
- 16 (cioè 17 - 1) divide 560
Ecco altri esempi di numeri di Carmichael con 3 o 4 fattori primi.
- 1105 = 5 × 13 × 17 ( 4 ∣ 1104 ; 12 ∣ 1104 ; 16 ∣ 1104 )
- 1729 = 7 × 13 × 19 ( 6 ∣ 1728 ; 12 ∣ 1728 ; 18 ∣ 1728 )
- 2465 = 5 × 17 × 29 ( 4 ∣ 2464 ; 16 ∣ 2464 ; 28 ∣ 2464 )
- 2821 = 7 × 13 × 31 ( 6 ∣ 2820 ; 12 ∣ 2820 ; 30 ∣ 2820 )
- 6601 = 7 × 23 × 41 ( 6 ∣ 6600 ; 22 ∣ 6600 ; 40 ∣ 6600 )
- 8911 = 7 × 19 × 67 ( 6 ∣ 8910 ; 18 ∣ 8910 ; 66 ∣ 8910 )
- 41041 = 7 × 11 × 13 × 41 ( 6 ∣ 41040 ; 10 ∣ 41040 ; 12 ∣ 41040 ; 40 | 41040 )
Dove a|b significa a divide b. Ad esempio 4|1104 significa 4 divide 1104.
Tutti i numeri soddisfano le tre condizioni del teorema di Korselt.
Note
Alcune note aggiuntive su questo teorema
- Tutti i numeri di Carmichael sono dispari
Se il numero \( n \) fosse pari e avesse un fattore primo dispari \( p \), allora \( p-1 \) sarebbe pari e non potrebbe dividere \( n-1 \), che è dispari. Questo implica che tutti i numeri di Carmichael devono essere necessariamente dei numeri dispari.
E così via
