Cenni di teoria dei numeri · Cenni di teoria dei numeri 6 ottobre 2011 ... In Nsi puµo deﬂnire...

Cenni di teoria dei numeri

6 ottobre 2011

AVVISO: I presenti appunti possono contenere (anzi sicuramente conterranno) errori e/oripetizioni. Essi sono infatti opera di vari collage e, per ovvie questioni di tempo, non sonostati rivisti. Pertanto non intendono sostituire alcun libro di teoria e/o esercizima vogliono sopratutto essere un dettagliato programma del corso. Prego gli studenti diprestare particolare attenzione nella loro lettura e di informarmi sia direttamente che pere-mail ([email protected]) su qualunque errore (certo o sospetto) notato.

Cerchero di correggere nel piu breve tempo possibile qualunque errore trovato. Pertantoquesti appunti saranno continuamente aggiornati: la data dell’ultimo aggiornamento apparein prima pagina. Consiglio infine agli studenti di non stamparli immediatamente mafarlo il piu tardi possibile (per lo meno alcuni giorni dopo che l’argomento sia stato trattatoa lezione).

1

Indice

1 Numeri naturali, interi relativi e principi d’induzione 3

2 Teorema di divisione, M.C.D. e m.c.m. 5

3 Decomposizione in fattori primi 10

4 Sistemi di numerazione in base b 14

5 Congruenze 16

6 Criteri di divisibilita 18

7 Equazioni di congruenze 19

8 Sistemi di congruenze 22

9 Il Piccolo Teorema di Fermat e una sua applicazione alla crittografia 33

2

1 Numeri naturali, interi relativi e principi d’induzione

Il numero naturale si presenta sotto due forme:

• cardinale, se risponde alla domanda: quanti? (ad es. quanti sono gli elementi di undato insieme?)

• ordinale, se risponde alla domanda: quale? (ad es. qual e il posto di un fissato elementoin un dato insieme ordinato?)

In entrambi i casi risulta difficile darne una definizione nominale, cioe mediante concettinoti. Euclide, ad esempio, definisce il numero naturale dicendo: “unita e tutto cio per cuiogni cosa e detta uno”, “numero e una moltitudine di unita”. Recentemente grazie a Peano(1858-1932) si e avuta una formulazione della definizione di numero naturale che risponde arequisiti logici.

Peano, premesso che i numeri naturali costituiscono la classe (=insieme) N = {0, 1, 2 . . .},fonda l’aritmetica (1881) sui tre concetti primitivi di:

zero, numero naturale, successivo

e sui seguenti cinque assiomi (noti come gli assiomi di Peano sui numeri naturali):

1. Zero e un numero naturale.

2. Il successivo n+ di un numero naturale n e un numero naturale.

3. Numeri naturali che hanno lo stesso successivo sono eguali.

4. Zero non e il successivo di alcun numero naturale.

5. (Assioma di induzione). Se P ⊆ N e tale che 0 ∈ P ed inoltre da n ∈ P segue n+ ∈ Pallora P = N.

Questi assiomi descrivono l’insieme N nel senso che le sue proprieta possono essere dedotteda essi. L’assioma 5 permette di dimostrare la seguente proposizione.

Proposizione 1.1 (Primo principio di dimostrazione per induzione). Sia P (n),n ∈ N, una successione di proposizioni dipendenti da n. Supponiamo che siano verificate ledue seguenti proprieta:

1. P (0) e vera;

2. P (n+) e vera ogni qualvolta e vera P (n).

Allora P (n) e vera per ogni n ∈ N.

3

Dimostrazione. (Dimostrazione obbligatoria) Chiamiamo P l’insieme dei numeri nper cui P (n) e vera. Allora per ipotesi abbiamo che 0 ∈ P e che se n ∈ P allora n+ ∈ P ;per l’assioma 5, l’insieme P coincide con N.

Dall’assioma di induzione segue anche il principio di definizione per induzione o ricorrenzache si applica per definire funzioni f : N→ M , dette successioni, essendo M un insieme nonvuoto qualunque. In base ad esso una funzione f : N → M e perfettamente determinataquando e assegnato il valore f(0) e una regola che permette di determinare f(n+) conoscendof(n).

Usiamo questo principio per definire somma e prodotto in N:

Somma

{0 +m = m;n+ +m = (n+m)+

; Prodotto

{0 ·m = 0;n+ ·m = n ·m+m

.

Si dimostra che per tali operazioni valgono le proprieta associativa, commutativa, dicancellazione, nonche la proprieta distributiva del prodotto rispetto alla somma.

• ∀x, y, z ∈ N, (x+ y) + z = x+ (y + z) e (xy)z = x(yz) (proprieta associativa);

• ∀x, y ∈ N, x+ y = y + x e xy = yx (proprieta commutativa);

• ∀x, y, z ∈ N, x+ y = z + y ⇒ x = z; xy = zy, y 6= 0 ⇒ x = z (legge di cancellazione);

• ∀x, y, z ∈ N, x(y + z) = xy + xz (proprieta distributiva del prodotto rispetto allasomma).

Si puo anche provare che, posto 0+ = 1, si ha n+ = n+ 1.In N si puo definire un ordinamento parziale, detto ordinamento aritmetico:

a ≤ b se esiste x ∈ N tale che b = a+ x.

E immediato verificare le tre proprieta dell’ordinamento parziale.

Teorema 1.1 N e ben ordinato con la relazione di ordinamento aritmetico.

Dimostrazione. (Dimostrazione facoltativa). Ricordiamo che un sottoinsieme di uninsieme parzialmente ordinato si dice ben ordinato se ogni suo sottoinsieme non vuoto ha ilminimo. Diamo due differenti dimostrazioni di questo teorema.Dimostrazione 1. Sia S ⊆ N, S non vuoto e sia M = {m | m ≤ s per ogni s ∈ S}. Si ha0 ∈ M ; inoltre se s ∈ S, s+ > s quindi s+ 6∈ M . Ne segue che M 6= N. Esiste allora perl’assioma 3, un numero m ∈ M , tale che m+ 6∈ M . Allora m ≤ s per ogni s ∈ S e m ∈ Sperche se fosse m 6∈ S sarebbe m < s per ogni s ∈ S e quindi m+ ≤ s per ogni s ∈ S cioem+ ∈ M contro l’ipotesi: m e quindi il minimo di S.Dimostrazione 2. Sia S ⊆ N un sottoinsieme privo di minimo; vogliamo dimostrareche e vuoto. Consideriamo la proprieta P (n): “Tutti i naturali ≤ n non stanno in S”;

4

evidentemente P (0) e vera, altrimenti 0 sarebbe il minimo di S. Supponiamo vera P (n) edimostriamo P (n+): quindi tutti i naturali ≤ n non stanno in S, e se ci stesse n+ allora essosarebbe il minimo di S. Quindi e vera P (n+) e per il primo principio d’induzione tutte leP (n) sono vere: segue che S e vuoto.

Indicheremo con Z = {. . . ,−2,−1, 0,+1,+2, . . .} l’insieme dei numeri interi relativi. Sipossono definire le operazioni di somma e prodotto tra numeri interi relativi in modo chevalgano proprieta analoghe a quelle dei numeri naturali. Il prodotto di zero per un qualunqueintero e uguale a zero; il prodotto di due interi relativi non nulli e uguale al prodotto dei lorovalori assoluti (come numeri naturali) preso con il segno piu o con il segno meno a secondache abbiano lo stesso segno oppure no; in particolare il prodotto di due numeri diversi da zeroe diverso da zero. Tale proprieta si esprime dicendo che in Z vale la legge di annullamentodel prodotto. Osserviamo che l’insieme Z si puo rendere parzialmente ordinato usando lastessa definizione della relazione aritmetica su N: si vede subito che ogni insieme del tipo{x ∈ Z | a ≤ x}, a ∈ Z fissato, e ancora ben ordinato.

Proposizione 1.2 Secondo principio di dimostrazione per induzione. Sia n0 unintero relativo fissato. Si consideri la successione di proposizioni P (n), n ≥ n0. Supponiamoche siano verificate le due seguenti proprieta:

1. P (n0) e vera;

2. se P (m) e vera per ogni m ∈ Z tale che n0 ≤ m < n, allora P (n) e vera.

Allora P (n) e vera per ogni n ≥ n0.

Teorema 1.2 Il secondo principio di induzione e equivalente al primo principio d’induzione.

2 Teorema di divisione, M.C.D. e m.c.m.

Teorema 2.1 Teorema di divisione in N. Siano a, b ∈ N con b > 0. Esiste un’unicacoppia q, r ∈ N tali che 0 ≤ r 0 allora esiste al piu una coppia (q, r) ∈ N× N tale che 0 ≤ r q2 abbiamob ≤ b(q1 − q2) = r2 − r1 ≤ r2 < b,

assurdo.

5

Se q1 < q2, moltiplicando per −1 entrambi i membri della (1), abbiamo

b ≤ b(q2 − q1) = r1 − r2 ≤ r1 < b,

assurdo.Segue necessariamente q1 = q2 e, per la (1), r1 = r2. Quindi (q1, r1) = (q2, r2).Proviamo adesso che per ogni a, b ∈ N con b > 0 esiste almeno una coppia (q, r) ∈ N×N

tale che 0 ≤ r < b e a = bq + r. Procediamo per induzione sul numero a usando il secondoprincipio di induzione sulla seguente successione di proposizioni P (a), a ∈ N,

P (a) =“Comunque fissato il numero intero positivo b, esiste almeno una coppia(q, r) ∈ N× N tale che 0 ≤ r 0, la coppia

(q, r) = (0, 0) verifica entrambe le condizioni 0 ≤ r = 0 < b e 0 = b0 + 0.Condizione 2. Bisogna provare che, comunque fissato a ∈ N, se P (a′) e vera per ogni

a′ tale che 0 ≤ a′ < a, allora P (a) e vera. Per fare cio distingueremo i due casi: a < b ea ≥ b. Si osservi che nel primo di essi proveremo la verita di P (a) senza far uso dell’ipotesiinduttiva.

Sia a < b. Poniamo (q, r) = (0, a). Si ha 0 ≤ r = a 0. Per l’ipotesi induttiva esiste (q, r), con 0 ≤ r ≤ b, tale che a − b = qb + r; si haallora a = (q + 1)b + r. Abbiamo quindi provato che la coppia (q + 1, r) e una soluzionedell’equazione a = bq + r con 0 ≤ r < b.

Dimostrazione 2. (Dimostrazione obbligatoria). Consideriamo l’insieme S = {a −bx | a− bx ≥ 0, x ∈ N}; S e non vuoto perche contiene a− b0 = a ∈ N e quindi ha minimo,diciamo r = a− bq per un certo q ∈ N. Se fosse r ≥ b allora sarebbe 0 ≤ r − b < r perche be positivo e r − b = a− b(q + 1), contro l’ipotesi che r e il minimo di S.

Teorema 2.2 Teorema di divisione in Z. Siano a, b due interi relativi, b 6= 0. Esisteun’unica coppia di interi q, r, con 0 ≤ r < |b|, tali che a = bq + r.

Definizione 2.1 Siano a, b ∈ Z, a 6= 0. Diciamo che “a divide b” e scriviamo a|b se esistec ∈ Z tale che b = ac.

Definizione 2.2 Massimo comune divisore. Siano a, b ∈ Z non entrambi nulli (cioealmeno uno dei due interi deve essere diverso da zero). Si chiama massimo comune divisore(MCD) della coppia a, b, un numero d ∈ Z tale che:

1. d|a e d|b;2. se c|a e c|b allora c|d.

6

Definizione 2.3 Minimo comune multiplo. Si chiama minimo comune multiplo (mcm)della coppia a, b ∈ Z, a 6= 0 e b 6= 0, un numero m ∈ Z tale che:

1. a|m e b|m;

2. se a|c e b|c allora m|c.

Teorema 2.3 Ogni coppia a, b ∈ Z, a2 + b2 > 0, ha al piu due massimi comune divisori,uno l’opposto dell’altro.

Dimostrazione. Supponiamo che d, d′ siano entrambi massimo comune divisore di a, b;dalla definizione segue d|d′ e d′|d quindi d = hd′, d′ = kd per certi h, k ∈ Z. Sostituendo siottiene d = hkd e, per cancellazione, hk = 1; segue h = k = 1 oppure h = k = −1 e ci sonoal piu due massimi comuni divisori di a, b uno opposto dell’altro. Quindi se d e massimocomune divisore lo e anche −d.

L’esistenza del massimo comune divisore verra provata nel teorema successivo. Ricordia-mo che ragionamenti analoghi valgono anche per il minimo comune multiplo.

Si suole indicare il massimo comune divisore positivo di a, b con MCD(a, b) oppure solo(a, b), il minimo comune multiplo positivo di a, b viene indicato con mcm(a, b) oppure [a, b].Si vede facilmente che per ogni coppia di interi non entrambi nulli a, b si ha:

(a, b) = (−a, b) = (a,−b) = (−a,−b), (2)

[a, b] = [−a, b] = [a,−b] = [−a,−b].

Lemma 2.1 Siano a, b, q, r ∈ Z tali che b 6= 0 e a = bq + r. Allora (a, b) = (b, r).

Dimostrazione. Posto d = (a, b), per la definizione di MCD si ha:1) d|a e d|b;2) se esiste c ∈ Z tale che c|a e c|b, allora c|d.

Proviamo adesso che d soddisfa alla definizione di massimo comune divisore della coppiab, r. Abbiamo per ipotesi r = a − bq. Siccome d divide sia a che b, otteniamo che d|r.Supponiamo ora che esista c ∈ Z tale che c|b e c|r. Dall’uguaglianza a = bq + r segue che cdivide a e, per la 2), c|d.

Teorema 2.4 Siano a e b due interi non entrambi nulli; allora esiste il massimo comunedivisore (a, b).

Dimostrazione. Supponiamo b 6= 0. Se a = 0 si ha (a, b) = |b| e il teorema e provato (siosservi che b e scritto in valore assoluto perche abbiamo convenuto che (a, b) > 0). Proviamoil teorema per a 6= 0. Per la (2), possiamo supporre nel seguito a > 0 e b > 0. Proviamo indue modi diversi l’esistenza di (a, b). Diamo due dimostrazioni di questo teorema entrambeobbligatorie.

7

Dimostrazione 1. Consideriamo l’insieme S = {ax + by | ax + by > 0, x, y ∈ Z}; esso enon vuoto perche contiene, per esempio, a2 + b2. Quindi ha minimo, sia esso d = ax + by.Verifichiamo che d = MCD(a, b). Poiche e d > 0, per il teorema di divisione risulta a = dq+rcon 0 ≤ r < d; se fosse r > 0 allora r = a − dq = a − (ax + by)q = a(1 − xq) − byq ∈ S equesto e contro l’ipotesi che d e il minimo di A. Quindi d|a ed analogamente si dimostra ched|b.

Se poi un intero c e tale che c|a, c|b allora sara a = ch, b = ck e sostituendo: d =chx+ cky = c(hx+ ky) cioe c|d.

Dimostrazione 2 . (Algoritmo di Euclide delle divisioni successive). Possiamosupporre a ≥ b > 0 (perche?). Applichiamo il teorema di divisione alla coppia a, b: a = bq+rcon 0 ≤ r < b; se r = 0 allora b = MCD(a, b), come si verifica facilmente. Altrimentipossiamo dividere b per r, ottenendo: b = rq1 + r1 e ripetere il ragionamento di prima. Cosıcontinuando si arriva ad un termine poiche b > r > r1 > . . . ≥ 0; abbiamo cosı il seguentequadro:

a = bq + r

b = rq1 + r1

r = r1q2 + r2

...............

rn−2 = rn−1qn + rn

rn−1 = rnqn+1

Vogliamo dimostrare che rn, l’ultimo resto non nullo, e il MCD di a, b. Infatti, applicandoil Lemma 2.1 alle precedenti uguaglianze, abbiamo: (a, b) = (b, r) = (r, r1) = (r1, r2) = . . .. . . = (rn−1, rn) = rn.

Identita di Bezout. Dalla Dimostrazione 1 del Teorema 2.4 risulta che, dati due interi nonentrambi nulli a, b, il loro massimo comune divisore d si puo scrivere

d = ax+ by

per certi interi relativi x, y. Ci riferiremo ad una tale relazione come all’identita di Bezout.

Definizione 2.4 Due interi non nulli a e b si dicono primi tra loro o coprimi se il loromassimo comune divisore (a, b) e uguale ad 1.

Esempio 2.1 Cercare (78, 18) col metodo delle divisioni successive e scrivere la relativaidentita di Bezout.

SVOLGIMENTO. Si ha78 = 18 · 4 + 6,

18 = 6 · 3 + 0.

8

Quindi (78, 18) = 6.Per l’identita di Bezout, dalle precedenti uguaglianze otteniamo

6 = 78− 18 · 4,

6 = 78 · 1 + 18 · (−4)

che e l’identita cercata.



231 = 8 · 28 + 7,

8 = 7 · 1 + 1,

7 = 1 · 7 + 0.

Quindi (701, 231) = 1.Per l’identita di Bezout, riscriviamo le precedenti uguaglianze (esclusa l’ultima) nel

seguente modo:8 = 701− 231 · 3,7 = 231− 8 · 28,1 = 8− 7 · 1.

Possiamo quindi scrivere (701, 231) = 1 = 8 − 7 · 1 = 8 − (231 − 8 · 28) = 29 · 8 − 231 =29(701− 231 · 3)− 231 = 29 · 701− 88 · 231. L’identita cercata e quindi

(701, 231) = 29 · 701 + 231 · (−88).



321 = 312 · 1 + 9,

312 = 9 · 34 + 6,

9 = 6 · 1 + 3,

6 = 3 · 2 + 0.

Quindi (3522, 321) = 3.

9

Per l’identita di Bezout, riscriviamo le precedenti uguaglianze (esclusa l’ultima) nelseguente modo:

3 = 9− 6 · 1,6 = 312− 9 · 34,9 = 321− 312 · 1,

312 = 3522− 321 · 10.Possiamo quindi scrivere (3522, 321) = 3 = 9− 6 · 1 = 9− (312− 9 · 34) · 1 = 9 · 35− 312 =(321−312·1)·35−312 = 35·321−36·312 = 35·321−36·(3522−321·10) = 395·321−36·3522.L’identita cercata e quindi

(701, 231) = 3522 · (−36) + 321 · (395).

3 Decomposizione in fattori primi

I numeri primi sono divisibili soltanto per 1 e per se stessi. Se ne stanno alloro posto nell’infinita serie dei numeri naturali, schiacciati come tutti fradue, ma un passo in la rispetto agli altri. Sono numeri sospettosi e solitarie per questo Mattia li trovava meravigliosi. Certe volte pensava che in quellasequenza ci fossero finiti per sbaglio, che vi fossero rimasti intrappolati comeperline infilate in una collana. Altre volte, invece, sospettava che anche aloro sarebbe piaciuto essere come tutti, solo dei numeri qualunque, ma cheper qualche motivo non ne fossero capaci.

Da La solitudine dei numeri primi di Paolo Giordano, Oscar Mondadori.

Definizione 3.1 Un numero p ∈ Z si dice primo se e diverso da 0, 1 e i suoi unici divisorisono 1 e p.

Si dimostra che:

1. Se p e un numero primo e p|ab allora p|a oppure p|b. Piu in generale: se p e un numeroprimo e p|a1a2 · · · ar allora p|ai per qualche i, 1 ≤ i ≤ r.

2. Se a|bc e (a, b) = 1 allora a|c;3. Siano a, b ∈ Z, a 6= 0, b 6= 0. Allora un minimo comune multiplo di a, b e

[a, b] =ab

(a, b).

Cioe assegnati due interi non nulli a, b, un loro minimo comune multiplo si ottienedividendo il prodotto ab per il loro MCD (a, b).

10

Teorema 3.1 (Teorema fondamentale dell’aritmetica). Ogni numero naturale stret-tamente maggiore di uno si fattorizza nel prodotto di numeri primi positivi in maniera unicaa meno dell’ordine dei fattori.

Esempio 3.1 Le decomposizioni in fattori primi di 100, 641, 999 e 1024 sono:

100 = 22 · 52,

641 = 641,

999 = 33 · 37,

1024 = 210.

Osserviamo che il teorema di decomposizione in fattori primi si estende facilmente aZ; infatti preso un numero minore di −1, il suo opposto ha una fattorizzazione in fattoripositivi. Basta allora cambiare di segno uno dei fattori; notiamo che in Z l’unicita delladecomposizione vale non solo a meno dell’ordine ma anche a meno del segno dei fattoriprimi.

Crivello di Eratostene. Ad Eratostene e attribuito il merito di aver scoperto il seguentealgoritmo, noto col nome crivello di Eratostene, per determinare tutti i numeri primi compresifra 1 ed n:

1. Scrivere, in ordine crescente, tutti gli interi da 1 ad n.

2. Cancellare 1.

3. Cancellare tutti i numeri rimasti nella lista che sono divisibili per 2, maggiori di 2 eminori od uguali ad n. Fra i numeri rimasti, cercare il piu piccolo intero x maggiore di2. Se questo intero non esiste il procedimento ha termine. Altrimenti avremo x = 3.

4. Cancellare tutti i numeri rimasti nella lista che sono divisibili per 3, maggiori di 3 eminori od uguali ad n. Fra i numeri rimasti, cercare il piu piccolo intero x maggioredi 3. Se esso non esiste il procedimento ha termine. Altrimenti avremo x = 5.

5. Cancellare, fra i numeri rimasti, tutti i multipli di 5 che sono maggiori di 5 e minoriod uguali ad n. Fra i numeri rimasti, cercare il piu piccolo intero x maggiore di 5. Seesso non esiste il procedimento ha termine. Altrimenti avremo x = 7.

6. Procedere in modo analogo ai passi precedenti fin quando si ottiene che il numero xnon esiste. Contare quanti interi si trovano nella lista dei numeri non cancellati (infattiessa coincide con l’elenco dei numeri primi compresi fra 1 ed n.

11

Si osservi che i passi 3, 4, 5, . . . , della precedente procedura sono ripetitivi cioe essi possonoessere unificati in una procedura ricorsiva del seguente tipo.

Passo 1. Si riceve in input una lista crescente di numeri L e un numero c ∈ L;

Passo 2 Se c = maxL la procedura ha termine (bisogna inserire qui una procedura diuscita). Se c < maxL, si determina c = min{t ∈ L | t > c} e si crea la nuova lista Lottenuta cancellando in L tutti i multipli di c che sono maggiori di c.

Passo 3. Ritornare al Passo 1 ponendo ivi L = L e c = c.

Esempio 3.2 Usando il crivello di Eratostene si prova che i numeri primi minori od ugualia 100 sono: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,89 e 97.

Dato un intero n, e molto importante avere un test veloce (molto piu veloce del crivello diEratostene) per determinare se esso e primo o no. Per esempio in criptologia sono necessarinumeri primi molto grandi per formare messaggi segreti. Una procedura abbastanza semplicee basata sul seguente teorema.

Teorema 3.2 Sia n un numero intero positivo. Se n non e primo allora esso ha un divisoreprimo minore od uguale a

√n.

Dimostrazione. (Dimostrazione obbligatoria). Per ipotesi n non e primo. Quindiesso ha un fattore a con 1 < a < n. Quindi, n = ab, con a > 1 e b > 1. Supponiamo chevalgano entrambe le disuguaglianze

a >√n, e b >

√n. (3)

Ne segue n = ab >√n · √n = n, assurdo. Quindi almeno una delle disuguaglianze in (3)

deve essere falsa. Per esempio la prima. Si ha allora

a ≤ √n.

Quindi a e un divisore di n maggiore di uno. Se a e primo, il teorema e provato. Se a non eprimo, avra un divisore primo c, con 1 < c < a ≤ √

n. Poiche c divide n, il teorema risultacompletamente provato.

Nota 3.1 In virtu del Teorema 3.2, n e primo se non e divisibile per nessun primo a ≤ √n.

Esempio 3.3 Provare che 101 e primo.

Si ha√101 = 10, 049875 . . .. Quindi i primi minori od uguali a

√101 sono 2, 3, 5 e 7. Si

vede subito che 101 non e divisibile per nessuno di essi, quindi, per il Teorema 3.2, e primo.

12

Si osservi che il modo piu banale per stabilire la primalita di n consiste nel verificare seesso e divisibile per ogni primo p < n. Quindi bisogna determinare l’insieme di tutti i primiminori di n. La procedura illustrata nella Nota 3.1 e sicuramente piu veloce in quanto richiedela ricerca di tutti i numeri primi minori od uguali a

√n. In ogni caso entrambe si basano sul

crivello di Eratostene e, per interi n grandissimi, non sono molto veloci. Recentemente, M.Agrawal, N. Kayal e N. Saxena (PRIMES is in P, Annals of Mathematics 160 (2004), 781-793) basandosi sul Piccolo teorema di Fermat (si veda il Teorema 9.2) hanno determinatoun test per stabilire in modo veloce se un intero e o no primo.

Nel presente contesto ci limitiamo a dare una semplice procedura per fattorizzare n ininteri primi che si basa sul Teorema 3.2.

Procedura per determinare la fattorizzazione di n in interi primi.

1. Si cerchi il piu piccolo primo p1 che divide n. Se p1 = n, allora la fattorizzazione en = n e la procedura ha termine. Se p1 < n, allora p1 ≤ √

n e si passa al puntosuccessivo.

2. Sia n1 =np1, cioe n = p1n1. Si cerchi il piu piccolo primo p2 che divide n1. Se p2 = n1,

allora la fattorizzazione e n = p1n1 e la procedura ha termine. Sia p2 < n1, allorap1 ≤ p2 ≤ √

n1 e si passa al punto successivo. Si osservi che la disuguaglianza p1 ≤ p2segue dal fatto che p2 e anche divisore di n.

3. Sia n2 =n1

p2, cioe n1 = p2n2 e quindi n = p1p2n2. Procedendo in modo simile al punto

2, si cerchi il piu piccolo primo p3 che divide n2. Se p3 = n2, allora la fattorizzazione en = p1p2n2 e la procedura ha termine. Sia p3 < n2, allora p2 ≤ p3 ≤ √

n2 e si procedein modo simile ponendo n3 =

n2

p3. Si osservi che esistera un i per cui ni risulta primo e

quindi il procedimento ha termine.

Esempio 3.4 Trovare la fattorizzazione in primi del numero n = 7007 usando la precedenteprocedura.

Il piu piccolo primo che divide n = 7007 e p1 = 7. Si ha quindi n = 7007 = 7 · 1001.Sia n1 =

np1

= 1001. Cerchiamo ora il piu piccolo primo p2 maggiore od uguale a p1 = 7che divide n1 = 1001. Si ha p2 = 7 e quindi n1 = 1001 = 7 · 143 e n = 7007 = 7 · 7 · 143 =72 · 143.

Sia n2 = n1

p2= 143. Si cerchi il piu piccolo primo p3 maggiore od uguale a 7 che divide

n2 = 143. Esso e p3 = 11. e quindi n2 = 143 = 11 · 13 e n = 72 · 143 = 72 · 11 · 13.Sia n3 =

n2

p3= 13. L’intero n3, essendo primo, coincide col piu piccolo primo p4 maggiore

od uguale a 11 che divide n3. Quindi il procedimento ha termine e la fattorizzazione 7007in interi primi e 72 · 11 · 13.

Teorema 3.3 Teorema di Euclide sui numeri primi. I numeri primi sono infiniti.

Dimostrazione. (Dimostrazione obbligatoria). Supponiamo per assurdo che tutti inumeri primi siano nell’insieme P = {p1, p2 . . . pn} e consideriamo il numero 1+ p1 · p2 · · · pn.

13

Esso non e primo perche e maggiore di tutti gli elementi di P ; allora avra un divisore primoq. Se q fosse un elemento di P allora q dividerebbe sia p1 · p2 · · · pn che 1 + p1 · p2 · · · pn equindi la loro differenza che fa 1: assurdo.

Il Teorema 3.3 ci dice che esistono infiniti primi. Come abbiamo visto un’altra domandae molto interessante: Sia n un intero positivo. Quanti numeri primi minori o uguali ad nesistono? Il seguente teorema e stato provato nel 1896 da Hadamard e de la Vallee-Poussin.

Teorema 3.4 Sia n un intero positivo e sia P = {p | p ≤ n, p e′ primo}. Allora

limn→+∞

|P |n

lnn

= 1.

4 Sistemi di numerazione in base b

Quando scriviamo il numero a = 3481 intendiamo esprimere sinteticamente la somma: a = 3·103+4·102+8·10+1 che e la rappresentazione in base 10 del numero a. Tale rappresentazionedei numeri si dice posizionale perche il valore di una cifra dipende dalla sua posizione. Labase 10 che si adopera usualmente e puramente convenzionale; piu in generale si potrebberappresentare lo stesso numero a in base b, come precisato nel seguente teorema.

Teorema 4.1 Per ogni intero b > 1 possiamo rappresentare un numero naturale a > 0 inmaniera unica in base b:

a = (rnrn−1 . . . r1r0)b = rnbn + rn−1b

n−1 + . . .+ r1b+ r0

con 0 ≤ ri 0.Si osservi che usualmente si rappresentano le cifre, cioe i numeri tra 0 e b− 1, con un unicosimbolo: ad esempio {0, 1} per b = 2, {0, 1, . . . , 9, A,B, . . . , F} per b = 16.

Dimostrazione. (Dimostrazione obbligatoria). Questa dimostrazione fornisce ancheun algoritmo per ottenere un numero in base b. Applicando ripetutamente il teorema didivisione, si divide a per b e poi il quoziente ancora per b e cosı via fino ad ottenere unquoziente uguale a zero. Sia esso, per esempio, qn. Allora a = (rnrn−1 . . . r1r0)b. Mostriamoqui di seguito il procedimento nei suoi dettagli. Per il teorema di divisione abbiamo

a = bq0 + r0.

Se q0 = 0 allora a = (r0)b = (a)b e il procedimento ha termine. Sia q0 > 0. Essendo b > 1, siha q0 < a e, per il teorema di divisione,

q0 = bq1 + r1.

Se q1 = 0 allora a = b(bq1 + r1) + r0 = br1 + r0 = (r1r0)b e il procedimento ha termine. Siaq1 > 0, allora q1 < q0 < a e

q1 = bq2 + r2.

14

Se q2 = 0 allora a = b2q1 + br1 + r0 = b2(bq2 + r2) + br1 + r0 = b2r2 + br1 + r0 = (r2r1r0)b e ilprocedimento ha termine. Sia q2 > 0, allora q2 < q1 < q0 < a e

q2 = bq3 + r2.

................

Cosı procedendo esistera un intero n tale che 0 < qn−1 < qn−2 < . . . < q1 < q0 < a e

qn−1 = b0 + rn.

La rappresentazione cercata e cosı

a = (rnrn−1 . . . r1r0)b.

Si osservi che l’unicita di questa rappresentazione deriva dall’unicita di quoziente e restonella divisione.

Ovviamente si possono effettuare le quattro operazioni in qualunque base. L’unica novitae che bisogna usare la tavola pitagorica di base b.

Esempi.

1. Scrivere 5 in base 2. E facile verificare che 5 = 1 · 22 + 0 · 21 + 1 · 20. Quindi 5 in base2 si scrive: (101)2.

2. Si ha 2749 = 2 · 103 + 7 · 102 + 4 · 101 + 9 · 100. Pertanto 2749 = (2749)10. Cioe,per convenzione, quando si scrive un numero in base 10 si omettono le parentesi el’indicazione della base.

3. Scrivere 375 in base 2. Abbiamo:

375 = 2 · 187 + 1 ⇒ q0 = 187, r0 = 1,

187 = 2 · 93 + 1 ⇒ q1 = 93, r1 = 1,

93 = 2 · 46 + 1 ⇒ q2 = 46, r2 = 1,

46 = 2 · 23 + 0 ⇒ q3 = 23, r3 = 0,

23 = 2 · 11 + 1 ⇒ q4 = 11, r4 = 1,

11 = 2 · 5 + 1 ⇒ q5 = 5, r5 = 1,

5 = 2 · 2 + 1 ⇒ q6 = 2, r6 = 1,

2 = 2 · 1 + 0 ⇒ q7 = 1, r7 = 0,

1 = 2 · 0 + 1 ⇒ q8 = 0, r8 = 1.

Quindi 375 in base 2 si scrive (101110111)2.

15

4. Scrivere 375 in base 4. Abbiamo:

375 = 4 · 93 + 3 ⇒ q0 = 93, r0 = 3,

93 = 4 · 23 + 1 ⇒ q1 = 23, r1 = 1,

23 = 4 · 5 + 3 ⇒ q2 = 5, r2 = 3,

5 = 4 · 1 + 1 ⇒ q3 = 1, r3 = 1,

1 = 4 · 0 + 1 ⇒ q4 = 0, r4 = 1.

Quindi 375 in base 4 si scrive (11313)4.

5 Congruenze

Definizione 5.1 Sia n un intero positivo fissato e siano a, b ∈ Z. Diciamo che a congruo bmodulo n, e scriviamo a ≡ b (mod n), se accade che a− b = kn per qualche k ∈ Z.In simboli, la definizione precedente si puo esprimere nel seguente modo:

a ≡ b (mod n) ⇔ n|a− b.

Ad esempio, posto n = 5, abbiamo:

7 ≡ 2 (mod 5),

14 ≡ 4 (mod 5),

−14 ≡ 1 (mod 5).

Se non e vero che a e congruo b modulo n, diremo che a non e congruo b modulo n escriveremo a 6≡ b (mod n). Ad esempio −14 6≡ 4 (mod 5).

Proposizione 5.1 Le seguenti proposizioni sono equivalenti:

1. a ≡ b (mod n);

2. a = b+ kn per qualche k ∈ Z;3. a e b hanno lo stesso resto se divisi per n.

Dimostrazione. (Dimostrazione obbligatoria).1 ⇒ 2: n|a− b vuol dire che a− b = kn per qualche intero k ∈ Z.2 ⇒ 3: Per il teorema di divisione in Z abbiamo a = nq1 + r1, 0 ≤ r1 < n, e b = nq2 + r2,0 ≤ r2 < n. Supponiamo inoltre r1 ≤ r2 (se r2 ≤ r1 si procede in modo analogo). Sostituendoin a = b+ kn si ottiene nq1 + r1 = nq2 + r2 + kn cioe 0 ≤ r1 − r2 = n(q2 − q1 + k) ≤ r1 < n.Quindi deve essere q2 − q1 + k = 0, da cui r1 = r2.3 ⇒ 1: Da a = nq1 + r, b = nq2 + r si ottiene a− b = n(q1 − q2).

16

Proposizione 5.2 Proprieta delle congruenze.

(1) Se a ≡ b (mod n) e a′ ≡ b′ (mod n), allora:

• a+ a′ ≡ b+ b′ (mod n),

• aa′ ≡ bb′ (mod n).

(2) Se a ≡ b (mod n) e d|n, allora a ≡ b (mod d).

(3) Se a ≡ b (mod n) e a ≡ b (mod m) allora a ≡ b (mod [n,m]).

(4) Se h 6= 0 e ha ≡ hb (mod n) allora a ≡ b (mod n(h,n)

).

Dimostrazione. (Dimostrazione obbligatoria).Proviamo la (1). Avendosi per ipotesi a− b = kn e a′ − b′ = k1n, abbiamo che:

• sommando membro a membro, si ha a+ a′ − (b+ b′) = (k + k1)n, cioe a+ a′ ≡ b+ b′

(mod n);

• moltiplicando membro a membro si ottiene aa′ = bb′ + bk1n + b′kn + kk1n2 = bb′ +

n(bk1 + b′k + kk1n) e quindi aa′ ≡ bb′ (mod n).

La (2) segue subito dalla proprieta transitiva della divisibilita. L’ipotesi della (3), per defini-zione, vuol dire che a− b e multiplo comune di n,m e quindi la tesi segue dalla definizione diminimo comune multiplo. Per la (4), sia d = (h, n) e quindi h = h′d, n = n′d con (h′, n′) = 1;poiche n|ha−hb = h(a− b), sostituendo si ottiene h′d(a− b) = kdn′ e quindi h′(a− b) = kn′

cioe n′|h′(a−b) da cui, essendo (h′, n′) = 1, n′|a−b. Osserviamo che, nel caso che (h, n) = 1,la (4) e una proprieta di cancellazione delle congruenze.

Proposizione 5.3 La congruenza in Z, fissato l’intero positivo n, e una relazione di equi-valenza.

Dimostrazione. (Dimostrazione obbligatoria). Valgono le proprieta:Riflessiva: a ≡ a (mod n). Infatti a− a = 0 = 0 · n.Transitiva: a ≡ b (mod n) e b ≡ c (mod n) ⇒ a ≡ c (mod n). Infatti a − b = k1n eb− c = k2n ⇒ a− c = (k1 + k2)n.Simmetrica: a ≡ b (mod n) ⇒ b ≡ a (mod n). Infatti a− b = kn ⇒ b− a = (−k)n.

Le classi disgiunte in cui Z viene ripartito dalla congruenza modulo n si sogliono denotarecon [0]n, [1]n, . . ., [n−1]n. L’insieme di tali classi, dette anche classi di resto modulo n, vieneindicato con Zn = {[0]n, [1]n, . . . , [n− 1]n}. Notiamo che le proprieta (1) della Proposizione5.2 permettono di definire operazioni di somma e prodotto in Zn:

[a]n + [b]n = [a+ b]n, [a]n · [b]n = [ab]n.

Tali operazioni sono ben definite, nel senso che il risultato non dipende dai rappresentantiscelti per le classi: se a′ ∈ [a]n e b′ ∈ [b]n allora [a′ + b′]n = [a+ b]n e [a′b′]n = [ab]n.

Completiamo il seguente paragrafo con le seguenti definizioni

17

Definizione 5.2 Siano x e d due interi e sia d > 0. Allora

1. x div d denota il quoziente q della divisione intera fra x e d;

2. x mod d denota il resto r della divisione intera fra x e d.

Ricordiamo che, per il teorema di divisione, esiste un’unica coppia di interi q e r taleche x = dq + r e 0 ≤ r < d. Allora q = x div d, e r = x mod d. E immediato provare lacongruenza

x ≡ r (mod d)

(perche?).

6 Criteri di divisibilita

Supponiamo di avere un numero a e la sua rappresentazione in base dieci:

a = rn10n + rn−110

n−1 + r110 + r0.

Le proprieta (1) e (2) delle congruenze della Proposizione 5.2 permettono di dimostrarealcuni criteri di divisibilita del numero a.

Teorema 6.1 Criterio di divisibilita per 9. Un numero a e divisibile per 9 se e solo se9 divide la somma delle cifre.

Dimostrazione. (Dimostrazione facoltativa). Poiche 10 ≡ 1 (mod 9) per la proprieta (2)si ha 10r ≡ 1 (mod 9) per ogni r ≥ 0, ed anche rs10

r ≡ rs (mod 9) (per la proprieta (1)) equindi a = rn10

n + rn−110n−1 + . . .+ r110 + r0 ≡ rn + rn−1 + . . .+ r1 + r0 (mod 9).

Osserviamo che se risulta a + b = c, ab = d per certi interi a, b, c, d ∈ Z, allora e anche[a]n + [b]n = [c]n, [a]n[b]n = [d]n per ogni intero positivo n. Questa proprieta puo essereusata per controllare l’esattezza delle operazioni tra interi, anche se e solo una condizionenecessaria. La ben nota prova del nove e basata sul precedente criterio: viene usato proprioil numero nove per la particolare facilita del calcolo del resto modulo nove.

Se un numero e divisibile per 9 allora lo e anche per 3.

Teorema 6.2 Criterio di divisibilita per 3. Un numero a e divisibile per 3 se e solo se3 divide la somma delle cifre.

Teorema 6.3 Criterio di divisibilita per 2 o per 5. Un numero a e divisibile per 2 oper 5 se l’ultima cifra e rispettivamente divisibile per 2 o per 5 (2|r0 oppure 5|r0).

18

7 Equazioni di congruenze

Consideriamo la seguente congruenza nell’incognita x:

x+ a ≡ b (mod n).

Essa si risolve facilmente, infatti essendo −a ≡ −a (mod n), sommando membro a membrosi ottengono le soluzioni x ≡ b−a (mod n) che possono essere scritte x = b−a+kn, ∀k ∈ Z.

Per esempio, le soluzioni dell’equazione x+ 2 ≡ 3 (mod 5) sono x ≡ 3− 2 (mod 5), cioex ≡ 1 (mod 5), e quindi x = 1 + 5k ∀k ∈ Z.

Piu interessante si presenta lo studio della seguente equazione (sempre nell’incognita x):ax ≡ b (mod n) con a 6= 0.

Teorema 7.1 Siano a, b ∈ Z con a 6= 0. Condizione necessaria affinche l’equazione,nell’incognita x ∈ Z,

ax ≡ b (mod n)

ammetta soluzioni e che (a, n)|b.

Dimostrazione. (Dimostrazione obbligatoria). Sia x una soluzione dell’equazioneax ≡ b (mod n). Allora esiste k ∈ Z tale che ax − b = kn. Posto d = (a, n), possiamoscrivere a = da′ e n = dn′ con (a′, n′) = 1. Abbiamo cosı da′x− b = kdn′, da′x+ kdn′ = b, equindi d|b.

Teorema 7.2 Siano a, b ∈ Z con a 6= 0. Se (a, n)|b allora l’equazione, nell’incognita x ∈ Z,

ax ≡ b (mod n). (4)

ha soluzioni. Inoltre, indicata con x e una sua soluzione, tutte le soluzioni di (4) sono

x = x+ kn

(a, n),

al variare di k ∈ Z o, equivalentemente, x ≡ x (mod n(a,n)

).

Dimostrazione. (Dimostrazione obbligatoria). Poniamo d = (a, n). Per ipotesi d|b,quindi b = b′d. Per l’identita di Bezout esistono x′, y′ ∈ Z tali che d = ax′+ny′. Moltiplicandoentrambi i membri di quest’ultima uguaglianza per b′, otteniamo b′d = ab′x′ + nb′y′, cioeb = a(b′x′) + n(b′y′). Posto x = b′x′, si ottiene ax − b = (−b′y′)n con −b′y′ ∈ Z. Quindix = b′x′ = b

(a,n)x′ e una soluzione della (4).

Proviamo che tutte le soluzioni della (4) sono date da x = x+ k n(a,n)

al variare di k ∈ Z.Si osservi innanzitutto che, per ogni k ∈ Z, x + k n

(a,n)e soluzione di (4). Infatti ax ≡ b

(mod n), in quanto x e una soluzione di (4), e k a(a,n)

n ≡ 0 (mod n). Quindi, per la (1) della

Proposizione 5.2, abbiamo a(x+ k n

(a,n)

)≡ b (mod n).

19

Sia ora x′ una soluzione di (4). Allora esistono k, h ∈ Z tali che

ax′ − b = kn, e ax− b = hn.

Sottraendo membro a membro, otteniamo

a(x′ − x) = (k − h)n.

Essendo d = (a, n), possiamo scrivere a = da′ e n = dn′. Abbiamo quindi

da′(x′ − x) = (k − h)dn′,

a′(x′ − x) = (k − h)n′.

Ne segue chen′|a′(x′ − x).

Essendo n′ e a′ primi fra loro,n′|x′ − x.

Cioe esiste ρ ∈ Z tale che

x′ − x = ρn′ = ρn

(a, n)

e quindi x′ ≡ x (mod n(a,n)

).

Esempio 7.1 Dire se l’equazione 4x ≡ 2 (mod 8) ha soluzioni.

SVOLGIMENTO. Poiche (4, 8) = 4 e 4 6| 2, per il Teorema 7.1 l’equazione data non hasoluzioni.

Esempio 7.2 Dire se l’equazione 4x ≡ 7 (mod 9) ha soluzioni e, in caso affermativo,determinarle.

SVOLGIMENTO. Essendo (4, 9) = 1, sicuramente 1|7 e quindi per il Teorema 7.1 l’equazionedata ammette soluzioni.

In virtu del Teorema 7.2, se x e una soluzione della nostra equazione, tutte le soluzionisono date da

x = x+ k9

(4, 9), ∀k ∈ Z.

Quindi il problema consiste nel determinare una soluzione particolare di 4x ≡ 7 (mod 9). Atale scopo basta procedere come nella dimostrazione del Teorema 7.2.Passo 1. Scrivere l’identita di Bezout relativa a 1 = (4, 9). Si ha

9 = 4 · 2 + 1, 4 = 1 · 4 + 0

e quindi1 = 9− 4 · 2,

20

1 = 9 + 4(−2)

che e l’dentita cercata.Passo 2. Moltiplicare entrambi i membri dell’identita di Bezout trovata al Passo 1 perb′ = 7

(4,9)= 7:

7 = 4(−14) + 9 · 7.Una soluzione particolare di 4x ≡ 7 (mod 9) e quindi x = −14.Passo 3. Tutte le soluzioni cercate sono

x = −14 + ρ9

(4, 9)= −14 + 9ρ, ∀ρ ∈ Z.

Queste soluzioni si possono anche scrivere come

x ≡ 4 (mod 9).

Esempio 7.3 Dire se l’equazione 40x ≡ 6 (mod 14) ha soluzioni e, in caso affermativo,determinarle.

SVOLGIMENTO. Essendo (40, 14) = 2, si ha che 2|6 e quindi per il Teorema 7.1 l’equazionedata ammette soluzioni.

In virtu del Teorema 7.2, se x e una soluzione della nostra equazione, tutte le soluzionisono date da

x = x+ k14

(40, 14)= x+ 7k, ∀k ∈ Z.

Quindi il problema consiste nel determinare una soluzione particolare di 40x ≡ 6 (mod 14).A tale scopo basta procedere come nella dimostrazione del Teorema 7.2.Passo 1. Scrivere l’identita di Bezout relativa a 2 = (40, 14). Si ha

40 = 14 · 2 + 12,

14 = 12 · 1 + 2,

12 = 6 · 2 + 0.

Quindi2 = 14− 12 · 1,12 = 40− 14 · 2

. Da cui 2 = 14− 12 · 1 = 14− (40− 14 · 2) · 1 = −40 + 14 · 3. L’identita cercata e dunque

(40, 14) = 2 = 40 · (−1) + 14 · 3.

Passo 2. Moltiplicare entrambi i membri dell’identita di Bezout trovata al Passo 1 perb′ = 6

(40,14)= 3:

6 = 40 · (−3) + 14 · 9.

21

Una soluzione particolare di 40x ≡ 6 (mod 14) e quindi x = −3.Passo 3. Tutte le soluzioni cercate sono

x = −3 + ρ14

(40, 6)= −3 + 7ρ, ∀ρ ∈ Z.

Queste soluzioni si possono anche scrivere come

x ≡ 4 (mod 7).

8 Sistemi di congruenze

Teorema 8.1 Siano n1 e n2 due interi positivi e siano a e b due interi relativi. Condizionenecessaria e sufficiente affinche il sistema di congruenze

{x ≡ a (mod n1)x ≡ b (mod n2)

(5)

ammetta soluzioni e che(n1, n2)|a− b.

Dimostrazione. (Dimostrazione obbligatoria). Osserviamo innanzitutto che risolvereil sistema (5) equivale a determinare l’insieme degli x ∈ Z tali che esiste una coppia ordinata(h, k) ∈ Z× Z per cui {

x = a+ hn1

x = b+ kn2.

Pertanto la dimostrazione di questo teorema e simile a quella dei Teoremi 7.1 e 7.2.Necessita. Sia x una soluzione di (5). Si ha x = a + hn1 e x = b + kn2. Ne segue

a− b = kn2 − hn1 = (n1, n2)[k n2

(n1,n2)− h n1

(n1,n2)

], quindi (n1, n2)|a− b.

Sufficienza. Supponiamo che (n1, n2)|a − b. Per l’identita di Bezout esistono h, k ∈ Ztali che (n1, n2) = n1h + n2k. Da cui a−b

(n1,n2)(n1, n2) =

(h a−b(n1,n2)

)n1 +

(k a−b(n1,n2)

)n2. Posto

h = h a−b(n1,n2)

e k = k a−b(n1,n2)

, abbiamo a− b = hn1 + kn2. Da cui a− hn1 = b+ kn2 = x e una

soluzione di (5).

Teorema 8.2 Sia x una soluzione del sistema (5) del Teorema 8.1. Allora tutte le soluzionidi (5) sono x = x+ k[n1, n2] al variare di k ∈ Z o, equivalentemente, x ≡ x (mod [n1, n2]).

Dimostrazione. (Dimostrazione obbligatoria). Si osservi innanzitutto che x+k[n1, n2]e soluzione di (5) per ogni k ∈ Z. Infatti x+ k[n1, n2]− a e multiplo di n1 e x+ k[n1, n2]− be multiplo di n2.

Sia ora x′ un’altra soluzione del sistema dato. Allora esistono h1, h2, k1, k2 ∈ Z tali che{

x′ = a+ h1n1

x′ = b+ k1n2, e

{x = a+ h2n1

x = b+ k2n2.

22

Da cui {x′ − x = (h1 − h2)n1

x′ − x = (k1 − k2)n2.

Quindi x′ − x, essendo multiplo di n1 e di n2, e multiplo del loro minimo comune multiplo[n1, n2]. Quindi x′ ≡ x (mod [n1, n2]).

Si osservi che il Teorema 8.2 fornisce una formula risolutiva del sistema (5) purche siriesca a determinarne una soluzione particolare x. Un algoritmo per trovare x e datonel corso della dimostrazione della sufficienza del Teorema 8.1.

Esempio 8.1 Dire se il seguente sistema ammette soluzioni ed, eventualmente, trovarle:

{x ≡ 3 (mod 8)x ≡ 2 (mod 6)

.

SVOLGIMENTO. Si ha (8, 6) 6| 3 − 2. Per il Teorema 8.1, il sistema assegnato non hasoluzioni.


{x ≡ 6 (mod 8)x ≡ 2 (mod 6)

.

SVOLGIMENTO. Si ha (8, 6) | 6− 2. Per il Teorema 8.1, il sistema assegnato ha soluzioni.In virtu del Teorema 8.2, tutte le soluzioni sono determinate non appena se ne conosce unaparticolare. Determiniamo quest’ultima. Sia x una soluzione particolare del sistema dato.Si ha {

x = 6 + 8hx = 2 + 6k

,

da cui 6 + 8h = 2 + 6k, e quindi

4 = 6k − 8h = 6k + 8(−h). (6)

L’identita di Bezout relativa a 2 = (6, 8) e 2 = 6 · (−1) + 8 · 1. Da cui 4 = 6(−2) + 8 · 2.Confrontando quest’ultima ugualglianza con la (6) abbiamo k = −2 e −h = 2. Quindix = −10. Tutte le soluzioni sono quindi x = −10 + k[6, 8],∀k ∈ Z, o, equivalentemente,x ≡ 14 (mod 24).

Esempio 8.3 Dire se il seguente sistema ammette soluzioni ed, eventualmente, determinar-le: {

6x ≡ 4 (mod 7)9x ≡ 8 (mod 4)

. (7)

23

SVOLGIMENTO. Risolvo la congruenza

6x ≡ 4 (mod 7). (8)

L’identita di Bezout relativa a (6, 7) e

1 = (6, 7) = 7 · 1− 6 · 1.Da cui

4 = 7 · 4− 6 · 4,6(−4) = 4 + 7(−4).

Una soluzione particolare e quindi x = −4. Tutte le soluzioni di (8) sono x ≡ −4 (mod 7),cioe

x ≡ 3 (mod 7). (9)

Risolviamo la seconda equazione del sistema

9x ≡ 8 (mod 4). (10)


1 = (9, 4) = 9 · 1− 4 · 2.Da cui

8 = 9 · 8− 4 · 16,9 · 8 = 8 + 4 · 16.

Una soluzione particolare e quindi x = 8. Tutte le soluzioni di (8) sono x ≡ 8 (mod 4), cioe

x ≡ 0 (mod 4). (11)

Adesso mettiamo a sistema (9) e (11):{

x ≡ 3 (mod 7)x ≡ 0 (mod 4)

. (12)


1 = (7, 4) = 7(−1) + 4 · 2.Da cui

3− 0 = 7(−3) + 4 · 6,3 + 7 · 3 = 0 + 4 · 6 = 24.

Una soluzione particolare e x = 24. Tutte le soluzioni di (12), e quindi di (7) sono

x ≡ 24 (mod 28).

24

Esempio 8.4 Dire se il seguente sistema ammette soluzioni ed, eventualmente, determinar-le: {

x ≡ 4 (mod 7)x ≡ 6 (mod 21)

.

SVOLGIMENTO. Si ha (7, 21) = 7 6 | − 2 = 4 − 6. Quindi, per il Teorema 8.1, il sistemaassegnato non ha soluzioni.

Il seguente teorema, di cui omettiamo la dimostrazione, generalizza il risultato dei Teo-remi 8.1 e 8.2.

Teorema 8.3 Siano ai, ni ∈ Z con ni > 0, i = 1, 2, . . . , k. Il sistema di congruenze

x ≡ a1 (mod n1)x ≡ a2 (mod n2). . .x ≡ ak (mod nk)

(13)

ammette soluzioni se e solo se (ni, nj)|ai − aj per ogni i, j ∈ {1, 2, . . . , k} con i 6= j.Inoltre, se x e una soluzione di (13), tutte le soluzioni sono

x ≡ x (mod µ)

essendo µ il minimo comune multiplo degli interi n1, n2, . . . , nk che indicheremo con[n1, n2, . . . , nk].

Un procedimento per risolvere (13) quando k ≥ 3, puo essere il seguente. Risolvere ilsistema {

x ≡ a1 (mod n1)x ≡ a2 (mod n2)

. (14)

Se (14) non ha soluzioni, neanche (13) avra soluzioni. In caso contrario le soluzioni di (14)sono del tipo x ≡ s1 (mod [n1, n2]) e si considera il seguente sistema

{x ≡ s1 (mod [n1, n2])x ≡ a3 (mod n3)

. (15)

Se (15) non ha soluzioni neanche il sistema (13) avra soluzioni. In caso contrario, le soluzionidi (15) sono del tipo x ≡ s2 (mod [n1, n2, n3]) e si considera il sistema

{x ≡ s2 (mod [n1, n2, n3])x ≡ a4 (mod n4)

.

Si procede cosı fino all’eventuale studio dell’ultimo sistema{

x ≡ sk−2 (mod [n1, n2, . . . , nk−1])x ≡ ak (mod nk)

.

L’eventuale soluzione di quest’ultimo coincidera con quella di (13).

25

x ≡ 4 (mod 5)x ≡ 2 (mod 4)x ≡ 6 (mod 9)

.

SVOLGIMENTO. Poniamo a1 = 4, a2 = 2, a3 = 6, n1 = 5, n2 = 4 e n3 = 9. Si ha(ni, nj) = 1 per ogni coppia i, j tale che 1 ≤ i < j ≤ 3. Pertanto (ni, nj)|ai − aj e, peril Teorem 8.3, il sistema dato ammette soluzioni che determiniamo mediante la proceduraillustrata prima. Cominciamo col risolvere il sistema

{x ≡ 4 (mod 5)x ≡ 2 (mod 4)

. (16)

Se x e una sua soluzione, avremo {x = 4 + 5kx = 2 + 4h

.

Da cui 4 + 5k = 2 + 4h, e quindi2 = 4h+ 5(−k). (17)

Per determinare un coppia h, k ∈ Z che risolva (17) procediamo nel seguente modo. Essendo(4, 5) = 1, si ricava facilmente che l’identita di Bezout e 1 = 4 · (−1) + 5 · 1. Moltiplicandoper 2, 2 = 4 · (−2) + 5 · 2. Pertanto una soluzione di (17) e h = −2, k = −2. Quindi x = −6e, per il Teorema 8.2, tutte le soluzioni di (16) sono x = −6 + 20t (poiche [4, 5] = 20) o,equivalentemente, x ≡ 14 (mod 20).

Si studia adesso il sistema seguente

{x ≡ 14 (mod 20)x ≡ 6 (mod 9)

. (18)

Se x e una sua soluzione, avremo

{x = 14 + 20kx = 6 + 9h

.

Da cui 14 + 20k = 6 + 9h, e quindi

8 = 9h+ 20(−k). (19)

Per determinare un coppia h, k ∈ Z che risolva (19) procediamo nel seguente modo. Si ha(20, 9) = 1. Determiniamone l’identita di Bezout. Si ha

20 = 9 · 2 + 2,

9 = 2 · 4 + 1,

26

2 = 1 · 2 + 0.

Quindi possiamo scrivere 1 = 9− 2 · 4 = 9− (20− 9 · 2) · 4 = 20 · (−4)+9 · 9. Da cui, α = −4e β = 9. Pertanto 1 = 20 · (−4) + 9 · 9 e l’identita cercata. Moltiplicando per 8, abbiamo8 = 20 · (−32) + 9 · 72. Pertanto una soluzione di (19) e h = 72, k = 32. Quindi x = 654e, per il Teorema 8.2, tutte le soluzioni di (18) sono x = 654 + 180t (poiche [20, 9] = 180) o,equivalentemente, x ≡ 114 (mod 180).

Essendo (18) l’ultimo sistema della nostra procedura, tutte le soluzioni del sistemaassegnato sono

x ≡ 114 (mod 180).


x ≡ 5 (mod 4)x ≡ 3 (mod 6)x ≡ 9 (mod 8)x ≡ 6 (mod 3)

. (20)

SVOLGIMENTO. Poniamo a1 = 5, a2 = 3, a3 = 9, a4 = 6, n1 = 4, n2 = 6 e n3 = 8, n4 = 3.Si verifica facilmente che (ni, nj)|ai − aj per ogni coppia i, j tale che 1 ≤ i < j ≤ 3. Allora,per il Teorema 8.3, (20) ammette soluzioni. Usiamo la precedente procedura per calcolarle.Cominciamo col risolvere il sistema

{x ≡ 5 (mod 4)x ≡ 3 (mod 6)

. (21)

Se x e una sua soluzione, avremo {x = 5 + 4hx = 3 + 6k

.

Da cui 5 + 4h = 3 + 6k, e quindi2 = 4(−h) + 6k. (22)

Per determinare un coppia h, k ∈ Z che risolva (22) procediamo nel seguente modo. Essendo(6, 4) = 2, si ricava facilmente che l’identita di Bezout e 2 = 6 · 1 + 4 · (−1). Pertanto unasoluzione di (22) e h = 1, k = 1. Quindi x = 9 e, per il Teorema 8.2, tutte le soluzioni di(21) sono x = 9 + 12t (poiche [4, 6] = 12) o, equivalentemente, x ≡ 9 (mod 12).

Si studia adesso il sistema seguente

{x ≡ 9 (mod 12)x ≡ 9 (mod 8)

. (23)

Per la (3) della Proprieta 5.2, le soluzioni di (23) sono x ≡ 9 (mod 24) (si osservi che[8, 12] = 24).

27

Si studia infine l’ultimo sistema{

x ≡ 9 (mod 24)x ≡ 6 (mod 3)

. (24)

Se x e una sua soluzione, avremo{

x = 9 + 24hx = 6 + 3k

.

Da cui 9 + 24h = 6 + 3k, e quindi

3 = 24(−h) + 3k. (25)

E immediato determinare un coppia h, k ∈ Z che risolva (25). Infatti (24, 3) = 3, cioe24 = 3 · 8 = 3 · 7 + 3 e 3 = 24 · 1 + 3 · (−7) e l’identita di Bezout. Pertanto una soluzionedi (25) e h = −1, k = −7. Quindi x = −15 e, per il Teorema 8.2, tutte le soluzioni di (24)sono x = −15 + 24t (poiche [24, 3] = 24) o, equivalentemente, x ≡ 9 (mod 24).

Essendo (24) l’ultimo sistema della nostra procedura, tutte le soluzioni di (20) sono

x ≡ 9 (mod 24).


2x ≡ 6 (mod 4)3x ≡ 7 (mod 5)4x ≡ 5 (mod 3)

. (26)

SVOLGIMENTO. Risolvo la congruenza

2x ≡ 6 (mod 4). (27)


2 = (4, 2) = 4 · 1 + 2 · (−1).

Da cui6 = 4 · 3 + 2 · (−3),

2(−3) = 6 + 4(−3).

Una soluzione particolare e quindi x = −3. Tutte le soluzioni di (27) sono x ≡ −3 (mod 2),cioe

x ≡ 1 (mod 2). (28)

Risolviamo la seconda equazione del sistema

3x ≡ 7 (mod 5). (29)

28


1 = (3, 5) = 3 · 2 + 5 · (−1).

Da cui7 = 3 · 14 + 5 · (−7),

3 · 14 = 7 + 5 · 7.Una soluzione particolare e quindi x = 14. Tutte le soluzioni di (29) sono x ≡ 14 (mod 5),cioe

x ≡ 4 (mod 5). (30)

Risolviamo infine la terza equazione del sistema

4x ≡ 5 (mod 3). (31)


1 = (1, 3) = 4 · 1 + 3 · (−1).

Da cui5 = 4 · 5 + 3 · (−5),

4 · 5 = 5 + 3 · 5.Una soluzione particolare e quindi x = 5. Tutte le soluzioni di (31) sono x ≡ 5 (mod 3),cioe

x ≡ 2 (mod 3). (32)

Adesso mettiamo a sistema (28), (30) e (32):

x ≡ 1 (mod 2)x ≡ 2 (mod 3)x ≡ 4 (mod 5)

. (33)

Ovviamente, l’insieme delle soluzioni del sistema assegnato coincide con quello di (33).Cominciamo col risolvere {

x ≡ 1 (mod 2)x ≡ 2 (mod 3)

. (34)


1 = (2, 3) = 3 · 1 + 2 · (−1).

Da cui2− 1 = 3 · 1 + 2 · (−1),

2 + 3 · (−1) = 1 + 2 · (−1) = −1.

29

Una soluzione particolare e x = −1. Tutte le soluzioni di (34) sono

x ≡ 5 (mod 6). (35)

Mettiamo ora a sistema (35) con (30):

{x ≡ 5 (mod 6)x ≡ 4 (mod 5)

. (36)


1 = (5, 6) = 6 · 1 + 5 · (−1).

Da cui5− 4 = 6 · 1 + 5 · (−1),

5 + 6 · (−1) = 4 + 5 · (−1) = −1.

Una soluzione particolare e x = −1. Tutte le soluzioni di (36), e quindi di (33) sono

x ≡ 29 (mod 30).

Il seguente teorema sembra (ed in effetti e) un caso particolare del Teorema 8.3. Nediamo la dimostrazione, in quanto essa fornisce un differente ed interessante algoritmo perdeterminare tutte le soluzioni del sistema di congruenze in esame.

Teorema 8.4 Teorema cinese del resto. Siano n1, n2, . . . , nk numeri interi positivi adue a due coprimi e a1, a2, . . . , ak numeri interi relativi. Allora il sistema di congruenze

x ≡ a1 (mod n1)x ≡ a2 (mod n2). . .x ≡ ak (mod nk)

(37)

ha soluzioni. Se x e una soluzione, allora tutte le soluzioni sono x ≡ x (mod M), doveM = n1n2 · · ·nk.

Dimostrazione. (Dimostrazione obbligatoria). Per i = 1, 2, . . . , k, poniamo Mi =Mni,

cioe Mi e il prodotto di tutti i moduli escluso ni. Poiche i moduli sono a due a due primi fraloro, abbiamo che (ni,Mi) = 1. Per il Teorema 7.2, l’equazione

Miy ≡ 1 (mod ni) (38)

ha soluzioni. Sia yi, i = 1, 2, . . . , k, una sua soluzione. Allora

x = a1M1y1 + a2M2y2 + . . .+ akMkyk (39)

30

e una soluzione del sistema (37). Infatti, essendo Mj ≡ 0 (mod ni) per ogni j 6= i, si ha

x ≡ aiMiyi (mod ni), (40)

ed essendo Miyi ≡ 1 (mod ni), si ha

aiMiyi ≡ ai (mod ni). (41)

Dalle (40) e (41) segue che x ≡ ai (mod ni) per ogni i = 1, 2, . . . , k, e quindi (39) e unasoluzione del sistema assegnato.

Dimostriamo ora che tutte le soluzioni del sistema sono date da x ≡ x (mod M). Siosservi innanzitutto che, per ogni ρ ∈ Z, x + ρM e soluzione di (37). Infatti, per ognii = 1, 2, . . . , k, x+ ρM − ai e multiplo di ni in quanto sia x− ai che M lo sono.

Sia ora x′ un’altra soluzione di (37). Allora

x′ = a1 + h1n1

x′ = a2 + h2n2

. . .x′ = ak + hknk

, e

x = a1 + t1n1

x = a2 + t2n2

. . .x = ak + tknk

.

Da cui

x′ − x = (h1 − t1)n1

x′ − x = (h2 − t2)n2

. . .x′ − x = (hk − tk)nk

e quindi

n1|x′ − xn2|x′ − x. . .nk|x′ − x

Allora x′ − x e multiplo di M (che e il minimo comune multiplo degli interi n1, n2, . . . , nk).Cioe x′ − x ≡ 0 (mod M), x′ ≡ x (mod M).

Osserviamo che, a differenza del Teorema 8.3, il teorema cinese del resto e solo unacondizione sufficiente per la risolubilita del sistema (37): puo effettivamente capitare cheesso abbia soluzioni anche se i moduli non sono a due a due coprimi.

La dimostrazione del teorema cinese del resto e particolarmente interessante perche pre-senta un semplice algoritmo per risolvere il sistema (37). Tale algoritmo consiste principal-mente nella ricerca di una soluzione particolare di ognuna delle congruenze (38) le qualinon dipendono dai termini noti ai ma solamente dai moduli ni. Questo e un validoaiuto nel caso in cui si debbano studiare piu sistemi di congruenze aventi gli stessi moduli,ovviamente a due a due primi fra loro, ma termini noti differenti.

31

Esempio 8.8 Determinare le soluzioni del seguente sistema applicando l’algoritmo fornitodal teorema cinese del resto:

x ≡ 4 (mod 5)x ≡ 6 (mod 4)x ≡ 2 (mod 9)

. (42)

SVOLGIMENTO. Poniamo a1 = 4, a2 = 6, a3 = 2, n1 = 5, n2 = 4, n3 = 9. Usando lostesso simbolismo del Teorema 8.4, abbiamo M = n1 · n2 · n3 = 180, M1 = n2 · n3 = 36,M2 = n1 · n3 = 45, M3 = n1 · n2 = 20.

Determiniamo una soluzione particolare y1 della congruenza M1y ≡ 1 (mod n1), cioe di

36y ≡ 1 (mod 5). (43)

La (43) equivale a36y + 5(−k) = 1.

Poiche (36, 5) = 1, abbiamo la seguente identita di Bezout 1 = 36 · 1 + 5 · (−7) e quindi

y1 = 1.


45y ≡ 1 (mod 4). (44)

La (44) equivale a45y + 4(−k) = 1.

Poiche (45, 4) = 1, abbiamo la seguente identita di Bezout 1 = 45 · 1 + 4 · (−11) e quindi

y2 = 1.


20y ≡ 1 (mod 9). (45)

La (45) equivale a20y + 9(−k) = 1.

Poiche (20, 9) = 1, abbiamo20 = 9 · 2 + 2,

9 = 2 · 4 + 1.

Pertanto 1 = 9− 2 ·4 = 9− (20−9 ·2) ·4 e l’identita di Bezout e 1 = 9 ·9+20 · (−4) e quindi

y3 = −4.

Per il Teorema 8.4, una soluzione di (42) e

x = a1M1y1 + a2M2y2 + a3M3y3 = 4 · 36 · 1 + 6 · 45 · 1 + 2 · 20 · (−4) = 254.

Tutte le soluzioni di (42) sono quindi x ≡ 254 (mod 180) o, e quivalentemente,

x ≡ 74 (mod 180).

32

Esempio 8.9 Determinare le soluzioni del seguente sistema applicando l’algoritmo fornitodal teorema cinese del resto:

x ≡ 4 (mod 5)x ≡ 2 (mod 4)x ≡ 6 (mod 9)

. (46)

SVOLGIMENTO. Il sistema assegnato coincide con quello dell’Esempio 8.5. Il metodo dirisoluzione e, ovviamente, differente.

Poniamo a1 = 4, a2 = 2, a3 = 6, n1 = 5, n2 = 4, n3 = 9. Si ha M = n1 · n2 · n3 = 180,M1 = n2 · n3 = 36, M2 = n1 · n3 = 45, M3 = n1 · n2 = 20. Si osservi che i moduli di (46)coincidono con quelli di (42). Poiche nell’algoritmo del teorema cinese del resto le congruenze(38) non dipendono dagli ai ma solamente dai moduli ni, abbiamo (si veda l’Esempio 8.9)

y1 = 1, y2 = 1, y3 = −4.

Una soluzione di (46) e

x = a1M1y1 + a2M2y2 + a3M3y3 = 4 · 36 · 1 + 2 · 45 · 1 + 6 · 20 · (−4) = −246.

Tutte le soluzioni di (42) sono quindi x ≡ −246 (mod 180) o, e quivalentemente,

x ≡ 114 (mod 180).

9 Il Piccolo Teorema di Fermat e una sua applicazione

alla crittografia

Il problema di determianre la cardinalita dell’insieme P dei numeri primi primi minori oduguali ad un fissato intero positivo n e molto difficile. Il miglior risultato in questo senso e,almeno fino ad oggi, dato dal Teorema 3.4. Piu facile risulta determinare, per ogni interopositivo n, la cardinalita dell’insieme dei numeri interi q, 1 ≤ q < n, che sono primi con n.Questo valore e noto come funzione di Eulero.

Definizione 9.1 Dicesi funzione di Eulero φ(n) quella funzione che fa corrispondere ad ogniintero positivo n il numero degli interi, compresi fra 1 e n, che sono primi con n.

Per comodita enunciamo il seguente teorema la cui dimostrazione si trova nel capitoloriguardante il Calcolo Combinatorio.

Teorema 9.1 Sia n un intero positivo avente la seguente fattorizzazione in fattori primin = pe11 pe22 . . . perr (unica a meno dell’ordine dei pi). Allora

φ(n) = n

(1− 1

p1

)(1− 1

p2

). . .

(1− 1

pr

).

33

Dimostriamo adesso il seguente risultato ricco di importanti conseguenze non solo teorichema anche applicative.

Teorema 9.2 Piccolo teorema di Fermat. Siano p un numero primo e x un interopositivo tali che x 6≡ 0 (mod p). Allora

xp−1 ≡ 1 (mod p).

Dimostrazione. (Dimostrazione obbligatoria).Sia A = {x mod p, 2x mod p, 3x mod p, . . . , (p − 1)x mod p} (si veda la Definizione 5.2).Cominciamo col dimostrare che gli elementi di A sono tutti distinti modulo p. Infatti sup-poniamo che per qualche coppia i, j con 1 ≤ j < i ≤ p − 1 si abbia ix mod p = jx mod p.Allora esistono k, h ∈ Z tali che ix−kp = jx−hp, cioe (i−j)x = (k−h)p e quindi p | (i−j)x.Il numero p, essendo primo, deve dividere almeno uno dei due interi x oppure i − j. Ma,essendo per ipotesi x 6≡ 0 (mod p), si ha p 6| x. Allora necessariamente p | (i− j), ma questoe assurdo perche 1 ≤ i− j < p.

Verifichiamo ora che 0 6∈ A. Infatti, se per qualche i ∈ {1, 2, . . . , p−1} fosse ix mod p = 0,ix dovrebbe essere un multiplo di p e quindi (essendo 1 ≤ i ≤ p − 1) p | x. Ma questocontraddice l’ipotesi x 6≡ 0 (mod p).

In conclusione abbiamo A = {1, 2, . . . , p−1}. Pertanto, per la (1) della Proposizione 5.2,

x · 2x · · · (p− 1) · x ≡ 1 · 2 · · · (p− 1) (mod p),

cioe[1 · 2 · 3 · · · (p− 1)] · xp−1 ≡ [1 · 2 · 3 · · · (p− 1)] (mod p).

Allora esiste h ∈ Z tale che 1 · 2 · 3 · · · (p− 1) · (xp−1 − 1) = hp, cioe

p | [1 · 2 · 3 · · · (p− 1) · (xp−1 − 1)]

.

Poiche p 6 | [1 · 2 · 3 · · · (p− 1)], si ha p | (xp−1 − 1) e quindi la tesi.

Il Piccolo Teorema di Fermat e un caso particolare del seguente teorema di cui omettiamola dimostrazione.

Teorema 9.3 Teorema di Eulero. Siano x e n interi positivi primi fra loro con n ≥ 2.Allora

xφ(n) ≡ 1 (mod n)

essendo φ(n) la funzione di Eulero.

Abbiamo gia precedentemente osservato come il miglior test di primalita (almeno fino-ra) scoperto si basi sul Teorema 9.2. Mostriamo adesso, in modo piu dettagliato, un’altrainteressantissima applicazione di questo teorema alla crittografia: l’algoritmo RSA.

Algoritmo RSA. (Dimostrazione obbligatoria). Inviare senza pericoli informazioniimportanti (per esempio numeri di carte di credito) attraverso Internet oggi e un problema di

34

cruciale interesse. L’informazione deve essere prima criptata, quindi codificata e trasmessa.Chi la riceve deve decodificarla e quindi decriptarla. Descriviamo brevemente come si puocriptare e poi decriptare un’informazione con un algoritmo sviluppato da Rivest, Shamir eAdleman nel lavoro A Method for obtainind Digital Signatures and Public-Key CryptosystemsComm. ACM 21 (1978), 120-126, (da qui la sigla RSA). Supponiamo di voler acquistare on-line un biglietto aereo pagandolo con la carta di credito. Chiaramente vogliamo trasmettereil numero n della carta di credito alla compagnia aerea in modo che eventuali intrusi nonpossano profittarne. E quindi necessario criptare n in modo che chi intercetta abusivamenteil messaggio non riesca a risalire ad n. D’altra parte la compagnia aerea deve essere in gradodi conoscere n (cioe deve poter decriptare il numero criptato da noi trasmesso). Ovviamentesono necessari due algoritmi: uno per criptare n trasformandolo per esempio nel numero med un altro per decriptare m e risalire ad n. In generale questi algoritmi sono pubblici mafanno uso di una chiave segreta per criptare e poi decriptare il messaggio. La compagniaaerea dovrebbe quindi assegnare ad ogni utente una chiave segreta personale e inviaglierlaattraverso un canale sicuro. Questa procedura, sebbene in molti altri casi possa funzionarebenissimo, sicuramente e impraticabile nel nostro esempio: ogni cittadino del mondo potreb-be acquistare online un biglietto! La compagnia aerea ha la necessita di rendere pubblica lachiave segreta e, nonostante questo fatto, l’intruso non deve essere in grado di decriptare ilmessaggio m inviato. Come si puo procedere? I metodi usati oggi si basano sull’algoritmoRSA.

La compagnia aerea sceglie due numeri primi p e q diversi tra loro e MOLTO MOLTOGRANDI. Quindi calcola r = pq e trova due interi positivi s e t tali che

st ≡ 1 (mod (p− 1)(q − 1)) (47)

(cioe st = j(p − 1)(q − 1) + 1 per qualche intero j) rendendo pubblici i numeri r e s (essiformano la chiave pubblica per criptare n).

Per esempio siano p = 37 e q = 23 (questi numeri sono troppo piccoli per un uso praticoma vanno bene per un esempio). Cosı, r = 37 · 23 = 851, e la compagnia aerea puo sceglieres = 5 e t = 317 perche 5 · 317 = 1585 = 2(36)(22) + 1 = 2(37 − 1)(23 − 1) + 1 ≡ 1(mod (37 − 1)(23 − 1)). Altre scelte per s e t sono possibili, ma in ogni caso si consigliadi evitare che uno di essi sia uguale ad 1. E importante osservare che la compagnia aereanon rende pubblici i numeri p, q e t ma solo r e s. Inoltre, data la grandezza di r = pq,possiamo supporre n < r. Invece di trasmettere n, l’utente calcola e invia il numero

m = ns mod r

(si veda la Definizione 5.2). Nascono le seguenti domande:

(1) La compagnia aerea che riceve m (cioe il numero n criptato) e in grado di risalire adn?

(2) L’intruso che intercetta m puo risalire ad n? (ovviamente anche lui conosce il valoredi r e t).

35

Cominciamo col rispondere alla prima domanda. Per risalire ad n, la compagnia aereadeve solo calcolare mt mod r. Proviamo infatti che vale la seguente uguaglianza:

mt mod r = n. (48)

Essendo 0 ≤ n < r, la (48) equivale a

mt ≡ n (mod r). (49)

Poiche m = ns mod r, abbiamo m ≡ ns (mod r) e, per la (1) della Proposizione 5.2,

mt ≡ nst (mod r). (50)

Vogliamo adesso provare le due seguenti congruenze:

nst ≡ n (mod p); (51)

nst ≡ n (mod q). (52)

Dimostriamo la (51). Si hanno due casi: n 6≡ 0 (mod p) oppure n ≡ 0 (mod p).Se n 6≡ 0 (mod p), per il Piccolo teorema di Fermat si ha np−1 ≡ 1 (mod p). Da cui,

sempre per la (1) della Proposizione 5.2,

(np−1

)j(q−1) ≡ 1 (mod p),

(np−1

)j(q−1)n ≡ n (mod p)

e quindi

nst = nj(p−1)(q−1)+1 =(np−1

)j(q−1)n ≡ n (mod p).

Se n ≡ 0 (mod p), allora nst−n e multiplo di p. Abbiamo cosı provato che, in ogni caso,la (51). Analogamente si prova la (52).

Essendo r = pq = [p, q], da (51) e (52) segue, per la (3) della Proposizione 5.2, che

nst ≡ n (mod r). (53)

Applicando la proprieta transitiva alle congruenze (50) e (53) (si veda la Proposizione5.3), otteniamo (49) e quindi (48).

Per quanto riguarda la seconda domanda, si osservi che la sicurezza di questo procedi-mento dipende dalla inaccessibilita di t. Essendo r e s pubblici, come mai t non puo esserededotto da chi vuole rubare il numero di carta di credito? Per conoscere t, l’intruso dovrebbeessere in grado di risolvere l’equazione (47) il cui modulo (p − 1)(q − 1) gli e sconosciuto.Per risalire ad esso dovrebbe individuare i numeri p e q conoscedone solo il prodotto r. Cioefattorizzare r = pq. Questo e, finora, un problema difficile (nel senso che la sua soluzionerichiede moltissimo tempo anche usando computer velocissimi). Nel nostro esempio e faci-lissimo fattorizzare r = 581. Ma, se p e q sono numeri di 200 cifre, il problema diventa perora quasi impossibile.

36

Indice analitico

(a, b), 7MCD(a, b), 7[a, b], 7a ≡ b (mod n), 16mcm(a, b), 7x mod d, 18

Algoritmo di Euclide delle divisioni successi-ve, 8

Algoritmo RSA, 34Assioma di induzione, 3Assiomi di Peano, 3

Classe resto modulo n, 17Congruo, 16Criterio di divisibilita per 2 o per 5, 18Criterio di divisibilita per 3, 18Criterio di divisibilita per 9, 18Crivello di Eratostene, 11

Equazioni di congruenze, 19

Funzione di Eulero, 33

Identita di Bezout, 8Insieme ben ordinato, 4Interi coprimi, 8Interi primi fra loro, 8

Massimo comune divisore, 6Minimo comune multiplo, 7

Numero naturale, 3Numero primo, 10

Piccolo teorema di Fermat, 34Principio di definizione per induzione o ricor-

renza, 4Principio di induzione, primo, 3Principio di induzione, secondo, 5Procedura per fattorizzare n, 13

Sistema di numerazione in base b, 14

Sistemi di congruenze, 22

Teorema cinese del resto, 30Teorema di divisione in N, 5Teorema di divisione in Z, 6Teorema di Euclide sui numeri primi, 13Teorema di Eulero, 34Teorema fondamentale dell’aritmetica, 11

37

Cenni di teoria dei numeri · Cenni di teoria dei numeri 6 ottobre 2011 ... In Nsi puµo deﬂnire...

Documents

Transcript of Cenni di teoria dei numeri · Cenni di teoria dei numeri 6 ottobre 2011 ... In Nsi puµo deﬂnire...