Massimo comun divisore Lemma 1.1

(1)

Antonino Salibra

Universit`a Ca’Foscari Venezia 18 Novembre 2019

Nel seguito indicheremo con Z l’insieme dei numeri interi.

Scriveremo talvolta a|b al posto di “a divide b”. Questo significa che esiste c ∈ Z tale che b = ac. Ricordiamo che ogni numero intero divide 0.

1. Massimo comun divisore

Lemma 1.1. Dati due interi a e b con b 6= 0, esiste un’unica coppia di interi q (quoziente) ed r (resto) tali che a = bq + r con 0 ≤ r < |b|, dove |b| `e il valore assoluto di b.

Proof. Consideriamo l’insieme A = {a − bz : z ∈ Z}. Sia r il minimo elemento ≥ 0 di A.

Allora esiste q ∈ Z tale che a = bq + r. Se fosse r ≥ |b|, allora 0 ≤ r − |b| < r. Se b > 0, allora a = b(q + 1) + (r − b), mentre se b < 0 allora a = b(q − 1) + (r − |b|). In ogni caso, r non sarebbe il minimo elemento ≥ 0 di A. Contraddizione.

Example 1.1. Se a = 17 e b = −3, allora 17 = (−3)(−5) + 2. Se a = −17 e b = −3 allora −17 = (−3)6 + 1.

Se a₁, . . . , a_n sono interi, allora a₁Z + · · · + anZ denota l’insieme di tutti gli interi che hanno la forma k1a1 + · · · + knan per opportuni k1, . . . , kn ∈ Z. Se a ∈ Z, allora aZ = {ka : k ∈ Z} `e l’insieme dei multipli di a. L’insieme a1Z + · · · + anZ si chiama ideale generato da a₁, . . . , a_n.

Consideriamo due esempi: 2Z + 3Z = Z perch´e 1 = 3 − 2 e quindi un arbitrario intero x si scrive come 3x + 2(−x), mentre lasciamo al lettore la verifica che l’ideale 4Z + 10Z `e l’insieme dei numeri pari.

Lemma 1.2. 1. a|b₁, . . . , a|b_n sse b₁Z + · · · + bⁿZ ⊆ aZ.

2. a = ±b sse bZ = aZ.

In particolare, abbiamo:

b `e un multiplo di a sse bZ ⊆ aZ e

a divide b sse aZ ⊇ bZ.

Per esempio, da 3 divide 6 segue che 3Z ⊇ 6Z. In altre parole, ogni multiplo di 6 `e anche multiplo di 3.

1

(2)

Lemma 1.3. Siano a e b numeri interi non entrambi nulli. Allora aZ + bZ = dZ, dove d `e il minimo intero positivo che appartiene all’ideale aZ + bZ.

Proof. Da d ∈ aZ + bZ si ricava d = xa + yb per opportuni x, y ∈ Z.

(dZ ⊆ aZ + bZ): Ogni multiplo di d si scrive come kd = (kx)a + (ky)b, da cui si ha dZ ⊆ aZ + bZ.

(aZ + bZ ⊆ dZ): Sia c ∈ aZ + bZ, ossia c = za + tb per opportuni z, t ∈ Z. Dividendo c per d si ottiene c = dq + r per opportuni q ed r tali che 0 ≤ r < d. Sostituendo c = za + tb e d = xa + yb si ricava: za + tb = c = qd + r = qxa + qyb + r. Quindi r = (z − qx)a + (t − qy)b ∈ aZ + bZ. Siccome d `e il minimo intero positivo in aZ + bZ, si deduce r = 0 e quindi c = dq ∈ dZ.

Ricordiamo che ogni numero intero a divide 0 perch´e 0 = a0.

Lemma 1.4. Siano a e b numeri interi. Allora esiste un unico numero d ≥ 0 che verifica le seguenti propriet`a:

(i) d|a e d|b;

(ii) Se c|a e c|b, allora c|d.

Se a, b sono non entrambi nulli, allora dZ = aZ + bZ.

Proof. Se a = b = 0, allora d = 0, perch´e 0 `e l’unico numero intero che ammette come divisori tutti i numeri interi.

Se a, b sono entrambi non nulli, definiamo d come il pi`u piccolo intero positivo tale che dZ = aZ + bZ (si veda Lemma 1.3). Allora, (i) segue da a, b ∈ aZ + bZ = dZ. Per provare (ii) notiamo che dall’ipotesi c|a e c|b segue che a, b ∈ cZ e quindi dZ = aZ + bZ ⊆ cZ.

Ossia c divide d.

Si noti che, se non utilizzassimo la teoria degli ideali, non sarebbe banale provare la propriet`a (ii) del lemma precedente.

Definition 1.1. Il massimo comun divisore (MCD) di a e b `e il pi`u grande divisore comune di a e b.

Il massimo comun divisore di a e b coincide con l’unico numero determinato dal Lemma 1.4. Verr`a indicato con MCD(a, b) oppure con (a, b).

Abbiamo (a, b) = (|a|, |b|), dove |a| e |b| sono il valore assoluto di a e b rispettivamente.

Dal Lemma 1.4 segue che (0, b) = b per ogni b ∈ Z.

Definition 1.2. Due numeri interi a, b si dicono relativamente primi se (a, b) = 1.

Un metodo efficiente di calcolo del massimo comun divisore `e l’algoritmo di Euclide.

Lemma 1.5. Siano a e b interi con b 6= 0 e sia a = bq + r con 0 ≤ r < |b|. Allora (a, b) = (b, r).

(3)

Proof. Abbiamo per ipotesi che bZ + rZ ⊆ aZ + bZ, perch´e r = a − bq ∈ aZ + bZ. L’altra inclusione aZ + bZ ⊆ bZ + rZ vale, perch´e a = bq + r. Allora, applicando il Lemma 1.4 si ottiene la conclusione: (b, r)Z = bZ + rZ = aZ + bZ = (a, b)Z.

Euclide(int a, int b) : int {int r;

while (b 6= 0) do //ripetere finch´e non riduciamo b a zero begin

r := mod_b(a) //resto della divisione di a per b;

a := b;

b := r;

end;

return a; //quando la variabile b diventa 0, il massimo comun divisore `e il valore della variabile a L’algoritmo consiste in una serie di divisioni con resto:

a = b · q₁ + r₂ 0 ≤ r₂ < |b|

b = r₂· q₂+ r₃ 0 ≤ r₃ < r₂ r2 = r3· q3+ r4 0 ≤ r4 < r3

r₃ = r₄· q₄+ r₅ 0 ≤ r₅ < r₄

... ... ...

r_t−2 = r_t−1· q_t−1+ r_t 0 ≤ r_t < r_t−1 r_t−1 = r_t· q_t+ 0 Allora r_t= (a, b)

(1)

Se indichiamo con C(a, b) il numero di volte che calcoliamo la divisione con resto nell’algoritmo di Euclide, allora in (1) di sopra abbiamo C(a, b) = t.

Example 1.2. C(a, 1) = 1 per ogni a > 1.

Example 1.3. (134, 36) = (36, 26) = (26, 10) = (10, 6) = (6, 4) = (4, 2) = (2, 0). In tal caso, C(134, 36) = 6.

Example 1.4. La successione di Fibonacci `e definita ricorsivamente come segue:

F₁ = 1; F₂ = 1; F_n = F_n−1+ F_n−2.

I primi elementi della successione sono: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . . . Il centounesimo numero di Fibonacci `e F101 = 354224848179261915075. Se dividiamo Fn+1

per F_n otteniamo proprio la relazione F_n+1 = F_n+ F_n−1, cioé il quoto è 1 ed il resto è F_n−1 < F_n. F_n+1 e F_n sono relativamente primi:

(Fn+1, Fn) = (Fn, Fn−1) = (Fn−1, Fn−2) = · · · = (F3, F2) = (2, 1) = 1.

n − 1 = C(F_n+1, F_n) `e il numero di volte che calcoliamo la divisione con resto.

Per definizione log₂(b) `e uguale al numero reale x tale che 2^x = b.

(4)

Lemma 1.6. Siano a > b interi positivi. Il numero di volte C(a, b) che iteriamo la divisione con resto nell’algoritmo di Euclide per il calcolo del massimo comun divisore (a, b) `e al pi`u 2log₂(b) + 2.

Proof. Siano r₀ = a e r₁ = b e

r₀ = r₁q₁+ r₂ 0 ≤ r₂ < r₁ r1 = r2q2+ r3 0 ≤ r3 < r2

r₂ = r₃q₃+ r₄ 0 ≤ r₄ < r₃ r₃ = r₄q₄+ r₅ 0 ≤ r₅ < r₄

... ... ...

r_t−2 = r_t−1q_t−1+ r_t 0 ≤ r_t< r_t−1 r_t−1 = r_tq_t

(2)

Proviamo che r_i > 2r_i+2, per ogni i ≥ 0. Infatti,

r_i = r_i+1q_i+1+ r_i+2 0 ≤ r_i+2< r_i+1

≥ r_i+1+ r_i+2 r_i > r_i+1 da cui segue q_i+1≥ 1

> 2r_i+2 r_i+2< r_i+1

(3)

Iterando il procedimento si ottiene:

b = r₁ > 2r₃ > 2²r₅ > · · · > 2^kr_2k+1.

Consideriamo il pi`u piccolo k tale che 2^k ≥ b > 2^k−1. Da 2^k ≥ b segue che r_2k+1 < 1, ossia r2k+1 = 0. In termini dell’algoritmo di Euclide (2) si ha rt+1 = 0, cos`ı abbiamo t + 1 ≤ 2k + 1, da cui t ≤ 2k. Inoltre vi sono esattamente t divisioni effettuate in (2), cos`ı l’algoritmo di Euclide termina in al pi`u 2k iterazioni. Allora si ha:

numero di iterazioni ≤ 2k = 2(k − 1) + 2 < 2log₂(b) + 2.

Il Lemma seguente spiega come l’algoritmo di Euclide ed i numeri di Fibonacci sono collegati.

Proposition 1.1. Siano a > b > 0 due numeri interi positivi tali che a = bq₁+ r₂, con 0 ≤ r₂ < b. Sia r₂ > r₃ > · · · > r_n > . . . la sequenza dei resti nell’algoritmo di Euclide applicato alla coppia di numeri a e b. Allora, valgono le seguenti condizioni:

1. Per ogni resto r_n6= 0, abbiamo

b ≥ F_n−1r_n−1+ F_n−2r_n > F_nr_n ≥ F_n,

dove F_n`e l’ennesimo numero di Fibonacci. Segue che se C(a, b) ≥ k (i.e., nell’algoritmo di Euclide il numero di divisioni con resto per il calcolo del MCD di a e b `e ≥ k), allora b > Fk.

L’esempio seguente fa capire l’efficienza dell’algoritmo di Euclide: se C(a, b) ≥ 101, allora b > F101 = 354224848179261915075.

(5)

Proof. Siano r0 = a > r1 = b due numeri interi positivi arbitrari. Allora, r0 = r1q1+ r2

con 0 ≤ r₂ < r₁, ed inoltre

r₁ = r₂q₂+ r₃, 0 ≤ r₃ < r₂.

Proveremo per induzione su n che b ≥ F_n−1r_n−1+ F_n−2r_n> F_nr_n. Iniziamo dal caso base.

Da q₂ > 0 si ottiene

b = r₁ ≥ r₂ + r₃ = F₂r₂+ F₁r₃ > 2r₃ = F₃r₃,

perch´e 0 ≤ r₃ < r₂ e F₁ = F₂ = 1. Supponiamo per ipotesi di induzione che b = r₁ ≥ F_n−1r_n−1+ F_n−2r_n> F_nr_n.

Proviamo che b = r1 ≥ Fnrn + Fn−1rn+1 > Fn+1rn+1. Da rn−1 = rnqn + rn+1 con 0 ≤ r_n+1< r_n si ha:

b = r₁

≥ F_n−1r_n−1+ F_n−2r_n by Ind. Hp.

= F_n−1(r_nq_n+ r_n+1) + F_n−2r_n by r_n−1 = r_nq_n+ r_n+1

≥ F_n−1(r_n+ r_n+1) + F_n−2r_n by q_n ≥ 1

= F_n−1r_n+ F_n−1r_n+1+ F_n−2r_n

= F_nr_n+ F_n−1r_n+1 by F_n= F_n−1+ F_n−2

> F_n+1r_n+1 by r_n > r_n+1.

Concludiamo la sezione con il Teorema di Bezout che determina le soluzioni delle equazioni lineari del tipo ax + by = c.

Lemma 1.7. Siano a, b numeri interi non entrambi nulli. Allora esistono interi x e y tali che ax + by = (a, b).

Proof. Dal Lemma 1.3 segue che aZ + bZ = dZ, dove d = (a, b) `e il massimo comun divisore di a, b.

Theorem 1.1. (Propriet`a di B´ezout) Siano a, b, c numeri interi e sia d = (a, b) il massimo comun divisore di a, b. Allora l’equazione lineare ax + by = c ha soluzioni intere sse d|c.

Proof. Dal Lemma 1.3 si ha aZ + bZ = dZ. Quindi c ∈ aZ + bZ sse c ∈ dZ.

Osservazione: Siano a, b interi non entrambi nulli. Allora l’equazione lineare ax + by = 0 rappresenta la retta dei vettori (x, y) che sono ortogonali al vettore (a, b). Dal Lemma 1.3 e dal Teorema di Bezout si ha che la retta ax + by = c parallela alla retta ax + by = 0 passa attraverso dei punti che hanno coordinate intere sse c `e un multiplo di (a, b).

Example 1.5. Trovare una soluzione intera dell’equazione 240x + 36y = 12. Possiamo dividere tutti i coefficienti per 12 ed ottenere 20x + 3y = 1. Siccome 20 e 3 sono relativamente primi (cio´e (20, 3) = 1) allora le soluzioni intere di 20x + 3y = 1 esistono. Si vede facilmente che x = −1 e y = 7 `e una soluzione di 20x + 3y = 1. La stessa soluzione risolve 240x + 36y = 12.

(6)

Example 1.6. Trovare una soluzione intera dell’equazione 120x + 81y = 12. Dividendo per 3 si ottiene 40x + 27y = 4. Siccome 40 e 27 sono relativamente primi (cio´e (40, 27) = 1) allora le soluzioni intere di 40x + 27y = 1 esistono. Applichiamo l’algoritmo di Euclide per il calcolo del massimo comun divisore: 40 = 27 + 13 e 27 = 13 ∗ 2 + 1. Quindi 1 = 27 − 13 ∗ 2 = 27 − (40 − 27) ∗ 2 = 27 − 40 ∗ 2 + 27 ∗ 2 = (−2)40 + 27 ∗ 3. Quindi una soluzione intera dell’equazione 40x + 27y = 4 `e: x = −8, y = 12. Le stesse soluzioni funzionano per l’equazione lineare 120x + 81y = 12.

Example 1.7. Non esistono soluzioni intere dell’equazione 6x + 2y = 5, perch´e 2 = (6, 2) non divide 5.

1.1. Massimo comun divisore e matrici

Ricordiamo che il minimo comune multiplo di due numeri interi positivi a e b è il più piccolo naturale k tale che a|k e b|k. È denotato da mcm(a, b). Si vede facilmente che

ab = mcm(a, b) × MCD(a, b).

Sia a > b > 0. Calcoliamo il massimo comun divisore e il minimo comune multiplo con il metodo matriciale. Consideriamo il sistema lineare

1 0 0 1

x y

=a b

(4)

Esso ammette banalmente come unica soluzione il vettorea b

. Sappiamo anche che ogni sistema lineare, che si ottiene dal sistema (4) applicando alla matrice completa

A =1 0 a 0 1 b

le regole del metodo di eliminazione di Gauss (scambio di due righe; sostituzione di una riga con la somma della riga stessa con un’altra moltiplicata per uno scalare r) ammette come unica soluzione il vettore a

b

.

Se a = bq + r con 0 ≤ r < b, si sottrae alla prima riga q volte la seconda riga e poi si scambiano la prima e la seconda riga:

1 0 a 0 1 b

⇒ 1 −q a − bq

0 1 b

=1 −q r

0 1 b

⇒ 0 1 b

1 −q r

Siccome b > r, si procede in maniera simile fino a quando nella terza colonna della matrice non appare uno 0 in posizione A₂₃. Alla fine otterremo una matrice

c d n e f 0

per cui il sistema lineare

c d e f

x y

=n 0

(7)

ha come unica soluzione il vettorea b

.

c d e f

a b

= ca + db ea + f b

=n 0

Allora n = ca + db `e il massimo comun divisore di a e b, mentre il modulo |ea| = |f b| `e il minimo comune multiplo.

L’algoritmo `e il seguente.

Matrice(nat a, nat b) {matrix A; nat q, z}

A :=1 0 a 0 1 b

;

while (A₂₃6= 0) do //ripetere finch´e non riduciamo A₂₃ a zero begin

q := ^A_A¹³

23 //quoto della divisione A₁₃= A₂₃q + r con resto 0 ≤ r < A₂₃;

for i := 1 to 3 do A_1i:= A_1i− qA_2i; //Sottrai q volte la riga 2 dalla riga 1 di A ; for i := 1 to 3 do z := A_1i; A_1i := A_2i; A_2i:= z; Scambia le righe 1 e 2 della matrice A;

end;

return A₁₃= A₁₁a + A₂b; // A₂₃ = 0 implica (a, b) = A₁₃ = A₁₁a + A₁₂b return A₂₁a = −A₂₂b; // A₂₃ = 0 implica mcm(a, b) = |A₂₁a| = | − A₂₂b|

Example 1.8. Calcoliamo il massimo comun divisore e il minimo comune multiplo di 53 e 71 con il metodo matriciale:

1 0 71 0 1 53

⇒ 0 1 53

1 −1 18

⇒ 1 −1 18

−2 3 17

⇒ −2 3 17

3 −4 1

⇒

3 −4 1

−53 71 0

Quindi,

3 −4

−53 71

71 53

=

3 × 71 − 4 × 53

−53 × 71 + 71 × 53

=1 0

da cui

(71, 53) = 1 = 3 × 71 − 4 × 53; mcm(71, 53) = 71 × 53.

Example 1.9. (134, 36) = (26, 36) = (26, 10) = (6, 10) = (6, 4) = (2, 4) = (2, 0) perch´e

1 0 134 0 1 36

⇒ 0 1 36

1 −3 26

⇒ 1 −3 26

−1 4 10

⇒ −1 4 10

3 −11 6

⇒ 3 −11 6

−4 15 4

⇒ −4 15 4

7 −26 2

⇒

7 −26 2

−18 67 0

Quindi,

7 −26

−18 67

134 36

=

7 × 134 − 26 × 36

−18 × 134 + 67 × 36

=2 0

da cui

(134, 36) = 2 = 7 × 134 − 26 × 36; mcm(134, 36) = 67 × 36 = 18 × 134 = 2412.

(8)

Example 1.10. Calcoliamo il massimo comun divisore di numeri di Fibonacci consecutivi (si veda esempio 1.4). Poniamo F−2 = 1 e F−1 = 0.

1 0 F_n 0 1 Fn−1

⇒ 0 1 F_n−1 1 −1 Fn−2

⇒ 1 −1 F_n−2

−1 2 Fn−3

⇒ −1 2 F_n−3 2 −3 Fn−4

⇒ 2 −3 F_n−4

−3 5 F_n−5

⇒ −3 5 F_n−5 5 −8 F_n−6

⇒ 5 −8 F_n−6

−8 13 F_n−7

⇒ . . .

Si noti che i numeri 2, 3, 5, 8, 13, . . . che compaiono nella matrice sono numeri di Fi- bonacci. In altri termini,

F−2 −F−1 F_n

−F−1 F₀ F_n−1

⇒ −F−1 F₀ F_n−1 F₀ −F₁ F_n−2

⇒ F₀ −F₁ F_n−2

−F₁ F₂ F_n−3

⇒ −F₁ F₂ F_n−3 F₂ −F₃ F_n−4

⇒ F₂ −F₃ F_n−4

−F₃ F₄ F_n−5

⇒ −F₃ F₄ F_n−5 F₄ −F₅ F_n−6

⇒ F₄ −F₅ F_n−6

−F₅ F₆ F_n−7

⇒ . . . Si noti che ad ogni passo abbiamo

F_2iF_n− F_2i+1F_n−1= F_n−(2i+2); F_2i−1F_n− F_2iF_n−1 = −F_n−(2i+1) Se n `e pari e 2i + 2 = n si ha

1 = F0 = Fn−2Fn− F_n−1² . Se n `e dispari e 2i + 1 = n si ha

F_n−1² −F_n−2F_n = 1 = (F_n, F_n−1); F_n−1F_n−F_nF_n−1 = F−1 = 0; mcm(F_n, F_n−1) = F_n−1F_n

2. L’aritmetica dell’orologio

L’aritmetica modulare (o aritmetica dell’orologio) `e stata introdotta da Gauss ad inizio ottocento. Consideriamo un orologio con n > 0 tacche che corrispondono ad i numeri da 0 a n − 1 (Si veda la figura nel caso n = 9). Indichiamo con Zⁿ l’insieme {0, 1, . . . , n − 1}. Scorriamo l’orologio in senso orario partendo da 0. Una mossa +1 consiste nello spostarsi in senso orario dalla tacca in cui ci troviamo alla tacca successiva. La mossa +1 corrisponde all’operazione di aggiungere 1. Quando arriviamo al numero n − 1 ed eseguiamo una ulteriore mossa +1, scopriamo che (n − 1) + 1 = 0 anzich´e (n − 1) + 1 = n.

Quindi, contrariamente ai numeri naturali, il numero 0 `e il successore del numero n − 1 e la funzione determinata dalle mosse +1 definisce una funzione bigettiva dall’insieme Zn nell’insieme Zn. Viceversa, scorriamo l’orologio in senso antiorario partendo da 0.

Una mossa −1 consiste nello spostarsi in senso antiorario dalla tacca in cui ci troviamo alla tacca precedente. La mossa −1 corrisponde a sottrarre 1. Quindi 0 − 1 = n − 1 anzich´e essere indefinito come avviene nell’aritmetica dei numeri naturali. La funzione determinata dalle mosse −1 definisce una funzione bigettiva dall’insieme Zn nell’insieme Zⁿ. Essa `e la funzione inversa della funzione determinata dalle mosse +1.

(9)

Figure 1. Aritmetica dell’orologio

Come possiamo “rappresentare” un intero a nell’orologio? Adottiamo due strategie diverse se a è positivo oppure negativo. Se a è positivo, eseguiamo esattamente un numero di mosse +1 pari ad a volte partendo da 0. La tacca in cui ci troviamo rappresenta il numero intero positivo a nell’orologio. Se a è negativo, eseguiamo esattamente un numero di mosse −1 pari ad |a| volte partendo da 0. La tacca in cui ci troviamo rappresenta il numero intero negativo a nell’orologio. In entrambi i casi la tacca del numero a rappresenta il resto della divisione di a per n che scriveremo

mod_n(a).

E un numero naturale compreso tra 0 e n − 1.`

Notazione: Talvolta scriveremo a mod n al posto di mod_n(a).

Definiamo la somma +_n (modulo n) ed il prodotto ∗_n (modulo n) sui numeri interi come segue:

a +_nb = mod_n(a + b); a ∗_nb = mod_n(ab).

Il risultato della somma e del prodotto `e sempre un valore compreso tra 0 e n − 1, quindi rappresentabile nell’orologio.

Lemma 2.1. L’insieme Zn= {0, 1, . . . , n − 1} `e chiuso rispetto alle operazioni di somma +_n e prodotto ∗_n.

Per semplificare i conti, utilizziamo la seguente proposizione

(10)

Proposition 2.1. Valgono le seguenti uguaglianze (a, b ∈ Z):

1. mod_n(a + b) = mod_n(mod_n(a) + mod_n(b));

2. mod_n(ab) = mod_n(mod_n(a) mod_n(b)).

Example 2.1. Sia n = 9. Allora mod₉(95 · 37) = mod₉(mod₉(95)mod₉(37)) = mod₉(5 · 1) = mod9(5) = 5. Se non avessimo utilizzato la proposizione avremmo dovuto calcolare mod₉(3515), che è più difficile specialmente se n è grande.

L’aritmetica dell’orologio `e correlata alla teoria delle congruenze che introduciamo nella prossima sezione.

3. Congruenze

Le tacche numerate dell’orologio della sezione precedente sono i rappresentanti delle n classi di equivalenza di una relazione di equivalenza ≡_ndefinita sugli interi. Nella prossima definizione introduciamo la relazione ≡n.

Definition 3.1. Sia n > 0. Diciamo che a, b ∈ Z sono congruenti modulo n, e scriviamo a ≡ b (mod n) oppure a ≡nb,

se mod_n(a) = mod_n(b).

Quindi abbiamo a ≡n b se il resto della divisione di a per n `e uguale al resto della divisione di b per n.

Lemma 3.1. Sia n > 0 e siano a e b numeri interi. Allora, a ≡_n b sse n divide b − a.

Proof. Supponiamo che a ≡_n b. Allora, dividendo a e b per n, si ha: a = q₁n + r e b = q₂n + r con 0 ≤ r < n. Ne segue che b − a `e divisibile per n: b − a = n(q₂− q₁).

Per la direzione opposta, supponiamo che b−a = nt per un opportuno t ∈ Z. Dividiamo sia a che b per n: a = q₁n + r₁ e b = q₂n + r₂ con 0 ≤ r₁, r₂ < n. Allora, b − a = n(q₂− q₁) + (r₂− r₁) = nt, da cui segue r₂− r₁ = n(t + q₁− q₂). Ma |r₂− r₁| < n. Quindi l’unica possibilit`a `e che r₁ = r₂.

Lemma 3.2. La relazione ≡_n `e una relazione di equivalenza su Z che `e compatibile rispetto alle operazioni di addizione, moltiplicazione e esponenziazione di interi:

(i) a ≡n b ∧ c ≡nd ⇒ a + c ≡n b + d.

(ii) a ≡_nb ∧ c ≡_n d ⇒ ac ≡_n bd.

(iii) a ≡_n b ⇒ a^k ≡_nb^k.

Proof. Sia mod_n(a) = mod_n(b) e mod_n(c) = mod_n(d).

(i) Dalla Proposizione 2.1(1) e dall’ipotesi si ha: modn(a + c) = modn(modn(a) + mod_n(c)) = mod_n(mod_n(b) + mod_n(d)) = mod_n(b + d).

(ii) La prova `e simile a quella del punto (i).

(iii) La prova `e per induzione su k utilizzando (ii).

(11)

La relazione ≡npartiziona Z in n classi di equivalenza. Se a `e un intero scriveremo [a]ⁿ per la classe di equivalenza di a modulo l’equivalenza ≡_n. Ecco la partizione determinata da ≡_n:

[0]_n= {kn : k ∈ Z}; [1]_n = {1 + kn : k ∈ Z}; . . . [n − 1]_n= {(n − 1) + kn : k ∈ Z}.

Scegliamo come rappresentanti delle classi di equivalenza i numeri 0, 1, 2, . . . , n − 1.

Questi numeri corrispondono alle tacche di un orologio che segna le ore da 0 sino ad n − 1 (si veda la figura con n = 4).

Figure 2. Aritmetica dell’orologio modulo 4

Le operazioni di somma +_n e prodotto ∗_n, definite nella sezione precedente, agiscono sulle classi di equivalenza modulo n tramite i loro rappresentanti.

Proposition 3.1. L’insieme Zn = {0, 1, 2, . . . , n − 1} con le operazioni di somma +_n e prodotto ∗_n modulo n costituisce un anello commutativo con unit`a. Questo significa che (Zⁿ, +n, 0) `e un gruppo commutativo rispetto alla somma:

• Propriet`a associativa: (x +ny) +nz = x +n(y +nz);

• Propriet`a commutativa: x +_ny = y +_nx;

• Elemento neutro: x +_n0 = x = 0 +_nx;

• Opposto: x +_n(−x) = 0 = (−x) +_nx.

(Zn, ∗_n, 1) `e un monoide commutativo rispetto al prodotto:

• Propriet`a associativa: (x ∗ny) ∗nz = x ∗n(y ∗nz);

(12)

• Propriet`a commutativa: x ∗ny = y ∗nx;

• Elemento neutro: x ∗_n1 = x = 1 ∗_nx;

Il prodotto distribuisce rispetto alla somma:

• x ∗_n(y +_nz) = (x ∗_ny) +_n(x ∗_nz).

Nei prossimi due lemmi studiamo propriet`a di cancellazione e periodicit`a delle potenze.

Lemma 3.3. Propriet`a di cancellazione: ac ≡_nbc ∧ (c, n) = 1 ⇒ a ≡_n b.

Proof. Dal Lemma 1.7 e dall’ipotesi (c, n) = 1 esistono interi x e y tali che cx + ny = 1.

Siccome cx = n(−y) + 1, allora cx ≡_n 1. Dal Lemma 3.2(ii) si ricava acx ≡_na e bcx ≡_nb.

Dall’ipotesi ac ≡_nbc segue che acx ≡_n bcx. Quindi a ≡_n b.

Lemma 3.4. Sia n > 0 ed a un intero. La sequenze di potenze modulo n

a⁰ a¹ a² a³ a⁴ a⁵ a⁶ . . .

1 mod_n(a¹) mod_n(a²) mod_n(a³) mod_n(a⁴) mod_n(a⁵) mod_n(a⁶) . . .

`

e periodica a partire da un certo punto in poi: esistono k e p ≤ n tali che a^k≡n a^k+rp per ogni r ≥ 0.

Example 3.1. Calcoliamo le potenze del 3 modulo 7:

3⁰ 3¹ 3² 3³ 3⁴ 3⁵ 3⁶

1 3 2 6 4 5 1

Il periodo `e 6. Per esempio 3² ≡ 3⁸. Infatti 3⁸ = 3²3⁶ ≡7 3². Example 3.2. Calcoliamo le potenze del 2 modulo 8:

2⁰ 2¹ 2² 2³ 2⁴

1 2 4 0 0

Il periodo `e 1 a partire da 2³.

Concludiamo la sezione con una serie di esempi che provano l’utilit`a della Proposizione 2.1 e dell’aritmetica modulare.

Example 3.3. Vogliamo calcolare qual’`e il resto della divisione di 95758 per 5. Siccome 10 `e divisibile per 5, si ha che 95758 = 8 + 5 · 10 + 7 · 10²+ 5 · 10³+ 9 · 10⁴ ≡₅ 8 ≡₅ 3.

Example 3.4. Vogliamo calcolare qual’`e il resto della divisione di 95758 per 7. Siccome 10 `e 3 modulo 7, si ha che

95758 = 8 + 5 · 10 + 7 · 10²+ 5 · 10³+ 9 · 10⁴

≡₇ 1 + 5 · 3 + 0 · 3²+ 5 · 3³+ 2 · 3⁴

≡₇ 1 + 15 + 5 · 3²· 3 + 2 · 3²· 3²

≡₇ 1 + 1 + 5 · 2 · 3 + 2 · 2 · 2

≡₇ 2 + 2 + 1 = 5

(13)

Example 3.5. Vogliamo determinare mod5(95758 · 37988). Piuttosto che eseguire prima la moltiplicazione e poi il calcolo del resto della divisione per 5, calcoliamo direttamente il resto della divisione di 95758 per 5 ed il resto della divisione di 37988 per 5. Si ha:

mod5(95758) = 3 e mod5(37988) = 3. Quindi mod5(95758 · 37988) = 4.

Example 3.6. Calcoliamo 3¹²⁸ modulo 7. Siccome 3³ = 27 ≡₇ −1, allora 3¹²⁸ = 3^3·42+2 = (3³)⁴²· 3² ≡₇ (−1)⁴²· 2 = 2.

4. Teoremi di Fermat e di Wilson

Pierre de Fermat, uno dei matematici più importanti dell’ultimo millennio, è nato il 17 agosto 1601 a Beaumont-de-Lomagne (Francia) ed è morto il 12 gennaio 1665 a Castres.

Era magistrato di professione e si occupava di matematica nel tempo libero. Presentiamo qui di seguito uno dei suoi risultati pi`u importanti.

Theorem 4.1. (Piccolo Teorema di Fermat) Se p `e un numero primo e p non divide a, allora a^p−1≡p 1.

Proof. Consideriamo i seguenti multipli positivi di a:

a, 2a, 3a, . . . , (p − 1)a.

Nessuno di questi numeri `e congruente ad un altro modulo p: se na ≡_p ma allora dal Lemma 3.3 potremmo cancellare a ed ottenere m ≡p n, che `e impossibile in quanto 1 ≤ n, m ≤ p − 1. Quindi i numeri a, 2a, 3a, . . . , (p − 1)a modulo p corrispondono in un qualche ordine ai numeri 1, 2, 3, . . . , p − 1. Si ha quindi:

a · 2a · 3a · · · (p − 1)a ≡_p 1 · 2 · 3 · · · (p − 1) da cui

a^p−1(p − 1)! ≡_p (p − 1)!

Cancellando (p − 1)!, che non `e divisibile per p, da entrambi i membri otteniamo la conclusione¹.

Corollary 4.1. Se p `e primo, allora a^p ≡_p a.

Example 4.1. Vogliamo calcolare 5²³⁶ modulo 13. Applicando il Piccolo Teorema di Fermat sappiamo che 5¹² ≡₁₃1. Quindi

5²³⁶ = 5^12·19+8 = (5¹²)¹⁹5⁸ ≡₁₃1¹⁹5⁸ = 5⁸ = (5²)⁴ ≡₁₃(−1)⁴ = 1

1Un’altra prova del Piccolo Teorema di Fermat si ottiene per induzione su a come segue. La base dell’induzione a = 1 `e ovvia. Supponiamo vero il teorema per a e dimostriamolo per a + 1:

(a + 1)^p=

p

X

i=0

( p!

i!(p − i)!)aⁱ

Siccome _i!(p−i)!^p! ≡_p0 per ogni 1 ≤ i ≤ p − 1 si ha:

(a + 1)^p≡_pa^p+ 1 ≡_pa + 1.

perch´e per ipotesi di induzione a^p≡pa.

(14)

Theorem 4.2. Se p e q sono primi distinti tali che a^p ≡q a e a^q ≡p a, allora a^pq ≡pq a.

Proof. Dal Corollario 4.1 si ha (a^p)^q ≡_q a^p e (a^q)^p ≡_p a^q. Per ipotesi a^p ≡_q a e a^q ≡_p a, quindi a^pq ≡_qa e a^pq ≡_p a. In conclusione p|a^pq− a e q|a^pq− a e quindi pq|a^pq− a.

Example 4.2. Consideriamo p = 11 e q = 31 numeri primi. Allora 2¹¹= 2 · 2¹⁰ = 2 · 2⁵· 2⁵ ≡₃₁2 · 1 · 1 = 2.

Per il Piccolo Teorema di Fermat si ha anche:

2³¹= 2(2¹⁰)³ ≡₁₁2 · 1³ = 2.

Applicando il teorema precedente si ha

2^11·31≡_11·31 2 che si pu`o anche scrivere

2³⁴¹ ≡₃₄₁2.

Theorem 4.3. Se p `e un numero primo, allora (Zp, +_p, 0, ∗_p, 1) `e un campo numerico.

Proof. Dalla Proposizione 3.1 dobbiamo soltanto provare che ogni elemento a ∈ Zp ha un inverso. La conclusione segue dal Piccolo Teorema di Fermat perch´e

aa^p−2 ≡_p 1.

Quindi a^p−2`e l’inverso di a.

Theorem 4.4. (Teorema di Wilson) Se p `e primo, allora (p − 1)! ≡_p −1.

Proof. Supponiamo p > 3 primo. Sia 1 ≤ a ≤ p − 1. Consideriamo la congruenza lineare ax ≡_p 1. Siccome a e p sono relativamente primi, questa congruenza ammette un’unica soluzione modulo p. Quindi esiste un unico a⁰ con 1 ≤ a⁰ ≤ p − 1 tale che aa⁰ ≡_p 1.

Dal fatto che p `e primo segue che a = a⁰ soltanto per a = 1 e a = p − 1. Infatti la congruenza quadratica a² ≡_p 1 si scrive a² − 1 = (a − 1)(a + 1) ≡_p 0. Si ricava a = 1 oppure p|a + 1 da cui a = p − 1.

Da tutto questo segue che

2 · 3 · · · (p − 2) ≡_p 1 che si scrive anche

(p − 2)! ≡_p 1.

Quindi

(p − 1)! = (p − 1) · (p − 2)! ≡_p p − 1 ≡_p −1.

Chiudiamo questa sezione con una applicazione del Teorema di Wilson allo studio delle congruenze quadratiche.

(15)

Theorem 4.5. Sia p un numero primo dispari. La congruenza quadratica x² ≡p −1 ammette una soluzione modulo p sse p ≡₄ 1.

Proof. (⇒) Supponiamo che esista a tale che a² ≡_p −1. Ricordiamo che p−1 `e un numero pari. Dal Piccolo Teorema di Fermat abbiamo:

1 ≡_p a^p−1= (a²)^p−1² ≡_p (−1)^p−1² .

Ne segue che ^p−1₂ `e pari e quindi p − 1 `e divisibile per 4. In altri termini, p ≡₄ 1.

(⇐) Supponiamo che p ≡₄ 1. Dal Teorema di Wilson abbiamo (p − 1)! ≡_p −1. Siccome

p−1

2 `e pari, allora possiamo dividere i numeri da 1 a p − 1 in due parti equinumeriche:

i numeri da 1 a ^p−1₂ , ed i numeri da ^p+1₂ a p − 1. Abbiamo che p − 1 ≡_p −1, p − 2 ≡_p

−2, . . . ,^p+1₂ ≡_p −^p−1₂ . Quindi

−1 ≡_p (p − 1)! ≡_p (p − 1

2 )!(−1)^p−1² (p − 1

2 )! = (p − 1 2 !)².

5. Teorema di Eulero

Leonhard Euler, noto in Italia come Eulero, è stato il più importante matematico del diciottesimo secolo. Eulero è nato il 15 aprile 1707 a Basilea in Svizzera ed è morto il 18 settembre 1783 a San Pietroburgo in Russia.

Si definisca la seguente funzione di Eulero:

φ(n) = numero di interi positivi ≤ n che sono relativamente primi con n.

Example 5.1. Se n `e primo, φ(n) = n − 1. Ecco altri esempi: φ(8) = 4 e φ(14) = 6.

Lemma 5.1. n `e primo sse φ(n) = n − 1.

Proof. Se φ(n) = n − 1 allora tutti i numeri da 1 a n − 1 sono relativamente primi con n.

Quindi, n `e primo.

Lemma 5.2. Se p `e primo, allora φ(p^k) = p^k− p^k−1 = p^k(1 −¹_p).

Proof. Si ha: (a, p^k) = 1 sse p 6 | a. Vi sono p^k−1 interi tra 1 e p^k che sono divisibili per p:

p, 2p, 3p, . . . , (p^k−1)p.

Quindi l’insieme {1, 2, . . . , p^k} contiene p^k− p^k−1 interi relativamente primi con p.

Per esempio, φ(9) = φ(3²) = 3²− 3¹ = 6.

Lemma 5.3. Se a e b sono relativamente primi, allora φ(ab) = φ(a)φ(b).

Proposition 5.1. Sia n > 0. L’insieme degli interi relativamente primi con n `e chiuso rispetto all’operazione di moltiplicazione (modulo n) e costituisce un gruppo moltiplicativo.

(16)

Proof. Sia (a, n) = 1 e (b, n) = 1. Allora si vede facilmente che (ab, n) = 1. Dal Lemma 1.7 esistono interi x, y tali che ax + ny = 1. Ne segue che ax ≡_n 1 ed x `e l’inverso di a.

Theorem 5.1. (Teorema di Eulero) Se n `e un intero positivo e (a, n) = 1, allora a^φ(n) ≡_n 1.

Proof. Siano b₁, b₂, . . . , b_φ(n) i numeri minori di n che sono relativamente primi con n.

Allora ab1, ab2, . . . , ab_φ(n) sono congruenti a b1, b2, . . . , b_φ(n) in qualche ordine. Ne segue che

(ab₁) · (ab₂) · · · (ab_φ(n)) = a^φ(n)(b₁· b₂ · · · b_φ(n)) ≡_nb₁ · b₂· · · b_φ(n)

Siccome ogni bi `e primo con n possiamo dividere per b1 · b2 · · · b_φ(n) ed ottenere la conclusione.

Example 5.2. φ(100) = φ(2² · 5²) = φ(2²)φ(5²) = 100(1 − ¹₂)(1 −¹₅) = 40. Dal teorema di Eulero si ricava

3⁴⁰ ≡₁₀₀1.

Quindi, per esempio, 3²⁵⁶ = 3^6·40+16 = (3⁴⁰)⁶3¹⁶ ≡₁₀₀ 3¹⁶. Infine, 3¹⁶ = (81)⁴ ≡₁₀₀ (−19)⁴ = (361)² ≡₁₀₀ 61² ≡₁₀₀ 21.

6. Equazioni modulari

Theorem 6.1. La congruenza lineare ax ≡_nb ha una soluzione sse (a, n)|b.

Proof. ax ≡_n b sse n|(ax − b) sse ∃q(ax − b = nq) sse ∃q(ax − nq = b). Dal Teorema 1.1 di B´ezout otteniamo che ax ≡_nb sse (a, n)|b.

Example 6.1. Vogliamo trovare, se esiste, una soluzione all’equazione modulare 124x ≡₇₁ 17. Siccome 124 ≡₇₁53, l’equazione si riduce a 53x ≡₇₁17. Calcoliamo il massimo comun divisore di 53 e 71 con il metodo matriciale:

1 0 71 0 1 53

⇒ 1 −1 18 0 1 53

⇒

1 −1 18

−2 3 17

⇒

3 −4 1

−2 3 17

⇒

3 −4 1

−53 71 0

Ne segue che 3 · 71 − 4 · 53 = 1. Siccome 1 divide 17, l’equazione modulare ha soluzione:

17 = 3 · 71 · 17 − 4 · 53 · 17 ≡₇₁53(−4 · 17), da cui si ricava x ≡₇₁ −4 · 17 = −68 ≡₇₁ 3.

Theorem 6.2. (Teorema cinese del resto) Siano n₁, . . . , n_k interi positivi a due a due relativamente primi (i.e., (n_i, n_j) = 1 per i 6= j). Allora il sistema di congruenze lineari

x ≡ a₁ (mod n₁) x ≡ a2 (mod n2) . . . .

x ≡ a_k (mod n_k)

ha una soluzione simultanea che `e unica modulo il prodotto n1× · · · × nk.

(17)

Diamo due differenti dimostrazioni del teorema.

Proof. Per ogni 1 ≤ i ≤ k si definisca

b_i = n₁. . . n_i−1n_i+1. . . n_k.

Si ha (b_i, n_i) = 1. Allora la congruenza lineare b_ix_i ≡_n_i 1 ha soluzione. Si noti che b_i ≡_n_j 0 per j 6= i. Allora il numero

x = a₁b₁x₁+ a₂b₂x₂+ · · · + a_kb_kx_k

risolve il sistema di congruenze lineari. Per esempio, x ≡_n₁ a₁b₁x₁ perch´e b₂, b₃, . . . , b_k ≡_n₁ 0. Inoltre, da b₁x₁ ≡_n₁ 1 si ottiene la conclusione x ≡_n₁ a₁. Lo stesso discorso vale per gli altri n_i.

Supponiamo che oltre ad x vi sia un’altra soluzione y. Allora si ricava facilmente che x ≡_n_i y per ogni 1 ≤ i ≤ k. Quindi, n₁. . . n_k divide x − y (si ricordi che (n_i, n_j) = 1 per i 6= j). Si conclude x ≡ y mod n₁× · · · × n_k.

Diamo un’altra prova del Teorema Cinese del resto utilizzando il Teorema di Eulero.

Proof. Per ogni 1 ≤ i ≤ k si definisca b_i = n₁. . . n_i−1n_i+1. . . n_k. Allora x = a₁(b^φ(n₁ ¹⁾) + a₂(b₂^φ(n²⁾) + · · · + a_k(b^φ(n_k ^k⁾) risolve il problema.

Example 6.2. Applichiamo il teorema cinese del resto per risolvere il seguente sistema di congruenze lineari:

x ≡₅ 2; x ≡₇ 6; x ≡₁₁3.

I numeri 5, 7, 11 sono primi tra loro (a due a due). Quindi, l’unica soluzione modulo 5 × 7 × 11 = 385 `e:

x = 2b₁x₁+ 6b₂x₂+ 3b₃x₃ dove

b₁ = 7 · 11 = 77; b₂ = 5 · 11 = 55; b₃ = 5 · 7 = 35, e x1, x2, x3 sono le soluzioni delle congruenze lineari

77x₁ ≡₅ 2x₁ ≡₅ 1; 55x₂ ≡₇ 6x₂ ≡₇ 1; 35x₃ ≡₁₁ 2x₃ ≡₁₁1.

Si ha x₁ = 3, x₂ = 6 e x₃ = 6. In conclusione,

x = mod₃₈₅(2 · 77 · 3 + 6 · 55 · 6 + 3 · 35 · 6) = 462 + 1980 + 630 = 3072 ≡₃₈₅ 377.

(18)

7. Applicazione alla Crittografia

Questa sezione `e essenzialmente la Sezione 4.6 del libro Bellissima-Montagna, Matem- atica per l’Informatica, Carrocci Editore, 2008.

Vogliamo inviare un messaggio privato ad un nostro interlocutore. Come prima cosa codifichiamo il messaggio con un numero M tramite una codifica elementare. Supponiamo di avere un alfabeto di n caratteri α₁, α₂, . . . , α_n. Associamo a ciascun carattere un numero in progressione evitando i numeri che nella rappresentazione in base 10 contengono degli zeri. Per ogni i, sia c_i il numero che codifica il carattere α_i. Allora una stringa α_i1. . . α_ik si codifica con il numero (in base 10) c_i10 . . . 0c_ik. La cifra 0 `e un separatore.

Example 7.1. Sia A = {a, b, c, d, e, f, g, h, i, l, m, n} l’alfabeto. Codifichiamo i caratteri con i numeri successivi 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14. Allora la stringa “cane” `e codifi- cata dal numero 40201406.

Un messaggio scritto con la codifica elementare può essere facilmente decodificato purché il nostro interlocutore conosca l’associazione carattere-numero. Questa associazione deve essere inviata al nostro interlocutore per mail e può quindi finire nelle mani di un intruso.

Per evitare il problema, criptiamo il messaggio.

Metodo 1 : Concordiamo con ciascuno dei nostri interlocutori una n-upla di numeri a₁, . . . , a_n a due a due relativamente primi. Tali numeri sono conosciuti soltanto allo scrivente ed agli interlocutori. Il Metodo 1 è basato sul Teorema Cinese del Resto: Sia m = a₁× . . . × a_n. Possiamo supporre che la codifica elementare M del nostro messaggio sia < m, altrimenti spezziamo il messaggio in più parti. Inviamo al nostro interlocutore non il numero M , ma i numeri b₁ ≡_a₁ M , b₂ ≡_a₂ M ,. . . , b_n ≡_a_n M . Chi riceve i numeri b₁, . . . , b_n può ricostruire M dal teorema Cinese del resto perché conosce a₁, . . . , a_n. Un eventuale intruso (che non conosce a₁, . . . , a_n) non potrebbe. Il metodo ha il problema di comunicare i numeri segreti a₁, . . . , a_n ai nostri interlocutori.

Metodo 2 : Questo metodo `e stato inventato nel 1977 da Ron Rivest, Adi Shamir e Leon Adleman ed `e indicato con la sigla RSA.

Ogni utente dispone di una chiave pubblica nota a tutti e una chiave privata. L’utente Pippo si procura quattro numeri distinti

p, q, n, e molto grandi tali che

• p e q sono numeri primi;

• n = p · q;

• e `e relativamente primo con p − 1 e q − 1 (per esempio, e potrebbe essere un numero primo maggiore di p e q).

I numeri p e q costituiscono la chiave privata nota solo all’utente Pippo, mentre i numeri n ed e costituiscono la chiave pubblica, utilizzata per inviare messaggi a Pippo. I numeri n ed e possono, per esempio, comparire nella home page del Signor Pippo.

(19)

In linea di principio, chi riuscisse a scomporre in fattori primi n potrebbe decodificare il messaggio, ma non esistono algoritmi efficienti per la scomposizione in fattori primi.

Il signor X vuole inviare un messaggio in codice a Pippo senza che nessuno lo possa decodificare. Il signor X considera la codifica elementare M del messaggio. Si pu`o supporre che M < n, altrimenti si spezza il messaggio in tante parti e si spediscono separatamente.

Possiamo supporre che M sia primo con n. Se no, si pu`o renderlo primo con n aggiungendo un simbolo speciale in fondo.

Il signor X cerca nella pagina web di Pippo la chiave pubblica di Pippo, ossia n ed e.

Il signor X calcola

modn(M^e).

Per calcolare questo numero si applicano le tecniche che abbiamo imparato nelle sezioni precedenti.

Il numero N < n tale che

N ≡_n M^e

costituisce il messaggio criptato che il signor X invia per email al signor Pippo. SOLO Pippo può decodificare N per ottenere M , quindi non è importante se qualcuno intercetta N . Determiniamo ora come Pippo può decodificare N .

Come Pippo decodifica N : Pippo calcola la funzione di Eulero φ(n) = φ(pq) = (p − 1)(q − 1). Poi l’utente Pippo risolve la congruenza modulare ex ≡_φ(n) 1. Tale congruenza modulare ammette soluzione perch´e e `e relativamente primo con φ(n) = (p − 1)(q − 1). Indichiamo con d una soluzione di tale equazione modulare. Successivamente Pippo calcola

mod_n(N^d).

Tale numero è la codifica elementare M del messaggio criptato. Infatti N^d ≡_n(Mê)^d ≡_n Mêd.

Ora essendo ed ≡_φ(n) 1, esiste un numero k tale che ed = 1 + kφ(n). Allora N^d≡_n (M^e)^d≡_nM^ed ≡_n M^1+kφ(n) = M (M^kφ(n)) = M (M^φ(n))^k ≡_nM per il Teorema di Eulero.

Un eventuale intruso per trovare M dovrebbe conoscere φ(n) = (p − 1)(q − 1), che `e impossibile da calcolare se non si conosce la scomposizione in fattori primi di n. Difficilissima da calcolare.