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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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