Home

Federica EU

1/10

Maria De Falco » 14.Numeri di Carmichael

Numeri di Carmichael: definizione e caratterizzazione

Definizione 14.1

Sia n un numero composto dispari.

Si dice che n è un numero di Carmichael se per ogni numero intero b coprimo con n, n è uno pseudoprimo rispetto a b.

Si ricordi che, se G è un gruppo, si dice che G ha esponente finito se esiste un numero intero positivo m tale che g^m=1 per ogni gєG.

Se G ha esponente finito e m è il minimo numero intero positivo tale che g^m=1 per ogni gєG, si dice che G ha esponente m.

Dunque, la Definizione 14.1 può essere riscritta nel modo seguente:

Definizione 14.1′

Sia n un numero composto dispari.

Si dice che n è un numero di Carmichael se l’esponente del gruppo Z_n* è un divisore di n-1.

Numeri di Carmichael: definizione e caratterizzazione

Teorema 14.2 (Criterio di Korselt, 1899)
Sia n un numero composto dispari.
Allora n è un numero di Carmichael se e solo se n è libero da quadrati e (p-1) divide (n-1) per ogni primo p che divide n.

Dimostrazione
Sia n un numero di Carmichael e si supponga per assurdo che esista un primo q tale che q² divida n.
Sia $[g]_{q^2}$ un generatore del gruppo ciclico $Z\integers _{q^2}^*$ . Sia q^k la massima potenza di q che divide n, e si consideri il sistema di equazioni congruenziali
$\left\{\begin{array}{l}x\equiv g(mod\; q^2) \\ \\ x\equiv 1 \left(mod\;\frac n{q^k}\right)\end{array}$

Numeri di Carmichael: definizione e caratterizzazione

Tale sistema ammette soluzioni per il Teorema Cinese del Resto; sia b una soluzione di tale sistema.
Allora b è coprimo sia con $q^2$ che con $\frac{n}{q^k}$
⇒ b è coprimo con n ⇒ bⁿ^-¹≡1 (mod n) e quindi bⁿ^-¹≡1 (mod q²), cioè

$[b]_{q^2}^{n-1}=[1]_{q^2}$ ⇒ n-1 è un multiplo del periodo di $[b]_{q^2}$ che è q(q-1)

⇒ q divide n-1: questa contraddizione prova che n è libero da quadrati.

Sia ora p un qualunque primo che divide n.

Sia [g]_p un generatore del gruppo ciclico Z_p*, e si consideri il sistema di equazioni congruenziali
$\left\{\begin{array}{l}x\equiv g(mod\; p) \\ \\ x\equiv 1 \left(mod\;\frac n p\right)\end{array}$
Tale sistema ammette soluzioni per il Teorema Cinese del Resto; sia b una soluzione di tale sistema.

Numeri di Carmichael: definizione e caratterizzazione

Allora b è coprimo sia con p che con $\frac{n}{p}$

⇒ b è coprimo con n ⇒ bⁿ^-¹≡1 (mod n) e quindi bⁿ^-¹≡1 (mod p), cioè $[b]_p^{n-1}=[1]_p$

⇒ n-1 è un multiplo del periodo di [b]_p che è p-1.

Viceversa, si supponga che sia n=p₁…p_t con p₁,…,p_t primi a due a due distinti e che per ciascun primo p_i , n-1 sia multiplo di p_i-1.

Sia b un qualunque numero intero coprimo con n ⇒ per ogni i=1,…,t $b^{p_i-1}\equiv 1 \; (mod \; p_i)$

⇒ per ogni i=1,…,t bⁿ^-¹≡1 (mod p_i) ⇒ bⁿ^-¹≡1 (mod n).

Dunque n è un numero di Carmichael.

Numeri di Carmichael: una proprietà

Proposizione 14.3

Sia n un numero di Carmichael.

Allora n è prodotto di almeno 3 primi distinti.

Dimostrazione

Si supponga per assurdo che sia n=pq con p e q primi tali che p<q.

Allora (n-1)-(p-1)=(n-p)=p(q-1); d’altra parte q-1 divide n-1 e quindi q-1 divide p-1; questa contraddizione prova l’asserto.

561 è un numero di Carmichael.
Infatti, 561=3∙11∙17 e i numeri 2,10,16 sono divisori di 560.

1105 è un numero di Carmichael.
Infatti, 1105=5∙13∙17 e i numeri 4,12,16 sono divisori di 1104.

1729 è un numero di Carmichael.
Infatti, 1729=7∙13∙19 e i numeri 6,12,18 sono divisori di 1728.

Numeri di Carmichael: un esercizio

Esercizio 14.4

Determinare tutti i numeri di Carmichael del tipo rpq, con r,p,q primi tali che r<p<q, e rє{3,5}.

SVOLGIMENTO DELL’ESERCIZIO

Sia n un numero di Carmichael tale che n=rpq, con r,p,q primi tali che r<p<q, e rє{3,5}.

Si verifica subito che (rpq-1)≡rp-1 (mod q-1); d’altra parte, rpq-1 è un multiplo di q-1, per il Teorema 14.2.

Ne segue che anche rp-1 è un multiplo di q-1, sicché esiste un numero naturale a tale che a(q-1)=rp-1.

Dato che q-1≥p e a(q-1)<rp, deve essere a<r; allora aє{2,…r-1}.

Numeri di Carmichael: un esercizio

Dalla relazione (rpq-1)≡rq-1 (mod p-1) e dal fatto che rpq-1 è un multiplo di q-1, segue che rq-1 è un multiplo di p-1.

Dunque anche a(rq-1) è un multiplo di p-1; d’altra parte, a(rq-1)=raq-a=r(a+rp-1)-a≡(r-1)(a+r) (mod p-1).

Ne segue che (r-1)(a+r) è multiplo di p-1.

In conclusione, fissato r, per ogni aє{2,…,r-1}, il primo p va scelto tra quelli per i quali il numero p-1 è un divisore di (r-1)(a+r).

Scelto p, il primo q è univocamente determinato dalla relazione a(q-1)=rp-1.

Dunque:

se r=3, l’unica possibilità è 3∙11∙17=561 (con a=2)
se r=5, le uniche possibilità sono 5∙29∙73=10585 (con a=2), 5∙17∙29=2465 (con a=3), 5∙13∙17=1105 (con a=4).

Osservazione 14.5

Dai risultati ottenuti nell’esercizio 14.4 segue, in particolare, che 561 è il minimo numero di Carmichael.

Un bound

Teorema 14.5

Sia n un numero composto dispari che non è un numero di Carmichael.

Allora
(1) l’insieme {bє N | 1≤b≤n-1, (b,n)=1, b^n-1≡1 (mod n)} ha ordine al più $\frac{\varphi (n)}{2}$
(2) se n non è libero da quadrati, l’insieme {bє N | 1≤b≤n-1, (b,n)=1, b^n-1≡1 (mod n)} ha ordine al più $\frac{n-1}{4}$
Dimostrazione
(1) L’insieme {bє N | 1≤b≤n-1, (b,n)=1, b^n-1≡1 (mod n)} è equipotente all’insieme
{[b]_n є Z_n* | [b]_n^n-1= [1]_n }, che è un sottogruppo proprio di Z_n* e quindi (per il Teorema di Lagrange) ha ordine minore o uguale di $\frac{\varphi (n)}{2}$ .
(2) Sia p un numero primo tale che p² divide n. Allora

l’insieme X= {bє N | 1≤b≤n-1, (b,n)=1, b^n-1≡1 (mod n)} è contenuto nell’insieme

Y= {bє N | 1≤b≤n-1, (b,p²)=1, b^n-1≡1 (mod p²)}.

Un bound

Si ha che l’insieme

$\{ [b]_{p^2} \in Z \integers _{p^2} \; \vert \; b\in Y \}$

è contenuto nell’insieme

$\{ [b]_{p^2} \in Z\integers _{p^2}^* \; \vert \; [b]_{p^2}^{n-1} = [1]_{p^2} \}$ ;

quest’ultimo insieme ha ordine (p(p-1), n-1) (cfr. Proposizione 5.10), che è un divisore di p-1 (poiché p e n-1 sono coprimi).
Quindi gli elementi di Y si distribuiscono in al più p-1 classi di congruenza modulo p².
D’altra parte, ogni classe di congruenza modulo p² è unione di $\frac{n}{p^2}$ classi di congruenza modulo n (cfr. Proposizione 3.1)
⇒ gli elementi di Y si distribuiscono in al più $\frac{n}{p^2}(p-1)$ classi di congruenza modulo n,
⇒ gli elementi di X si distribuiscono in al più $\frac{n}{p^2}(p-1)$ classi di congruenza modulo n;

Un bound

D’altra parte gli elementi di X sono a due a due incongrui modulo n, sicché X ha ordine al più $\frac{n}{p^2}(p-1)$ ; l’asserto segue infine dal fatto che

$\frac{n-1}{p^2-1}(p-1)=\frac{n-1}{p+1} \leq \frac{n-1}{4}$ .

Diversi autori si sono occupati del problema della distribuzione dei numeri di Carmichael, cioè della possibilità, fissato un numero naturale a, di limitare l’ordine dell’insieme

{nєN | 1≤n≤a , n è un numero di Carmichael}

E’ stato provato da Alford, Granville e Pomerance nel 1994 (W. R. Alford, A. Granville, C. Pomerance:

“There are infinitely many Carmichael numbers”,

Annals of Mathematics 140 (1994), 703-722) che esistono infiniti numeri di Carmichael e che questi sono “abbastanza frequenti”, nel senso che se a è un numero naturale sufficientemente grande, allora l’insieme

{nєN | 1≤n≤a , n è un numero di Carmichael} ha ordine almeno $a^{\frac{2}{7}}$