Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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 gm=1 per ogni gєG.

Se G ha esponente finito e m è il minimo numero intero positivo tale che gm=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 Zn* è 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 q2 divida n.
Sia [g]_{q^2} un generatore del gruppo ciclico Z\integers _{q^2}^*. Sia qk 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  ⇒  bn-1≡1 (mod n) e quindi bn-1≡1 (mod q2), 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 Zp*, 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  ⇒  bn-1≡1 (mod n) e quindi bn-1≡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=p1…pt con p1,…,pt primi a due a due distinti e che per ciascun primo pi , n-1 sia multiplo di pi-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  bn-1≡1 (mod pi ) ⇒ bn-1≡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, bn-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, bn-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, bn-1≡1 (mod n)} è equipotente all’insieme
{[b]n є Zn*  |  [b]nn-1 = [1]n }, che è un sottogruppo proprio di Zn* 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 p2 divide n. Allora

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

Y= {bє N | 1≤b≤n-1, (b,p2)=1, bn-1≡1 (mod p2)}.

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 p2.
D’altra parte, ogni classe di congruenza modulo p2 è 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}}

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion