Teoria dei numeri e Crittografia: lezione del 20 aprile 2011 Compatibilità della congruenza con somma e prodotto di interi.
Fissato il modulo intero m>1, e comunque dati gli interi relativi a,b,c,d , da:
ab (mod m), cd (mod m) seguono sempre:
a+cb+d (mod m) (compatibilità della congruenza rispetto alla somma) acbd (mod m) (compatibilità della congruenza rispetto al prodotto)
Infatti da m(a-b), m(c-d) si ha che esistono interi relativi h,k tali che a-b=hm, c-d=km da cui:
(a+c)-(b+d)=(h-k)m ac-bd=a(c-d)+d(a-b)=(ak+dh)m e si hanno le tesi m(a+c)-(b+d), mac-bd.
In particolare, comunque fissato un intero relativo y , da ab (mod m) seguono sempre:
a+yb+y (mod m) ayby (mod m)
(basta ricordare che per la proprietà riflessiva si ha yy (mod m)) Congruenze di primo grado ad una incognita.
Fissato il modulo m>1 e i numeri interi relativi a,b, poniamoci il problema di trovare (se esistono) tutti e soli gli interi relativi x tali che axb (mod m) . Diremo anche che tali valori x sono le soluzioni della congruenza axb (mod m) di primo grado nell’incognita x.
Sostituendo eventualmente a,b con le loro riduzioni modulo m, e sfruttando la compatibilità della congruenza rispetto alla somma e al prodotto, possiamo ricondurci al caso in cui a,b siano 0 (ed anche <m). Per evitare casi banali supporremo anche a>0.
Vediamo quando una soluzione della congruenza di primo grado esiste:
Teorema.
Fissato il modulo m>1 e i numeri interi a,b 0, con a>0, e posto d=mcd(a,m):
esiste una soluzione x della congruenza axb (mod m) d é divisore di b.
Dimostrazione:
(): Se axb (mod m), si ha ax-b=km, con kZ, da cui, essendo da, dm, ovviamente db.
(): Se db, posto dt=b, con tZ, e posto d=mcd(a,m)=az+mw, con z,wZ, si ottiene b=dt=azt+mwt, da cui aztb (mod m), e basta porre x=zt per ottenere una soluzione della congruenza.
Osservazione. Dal punto di vista algoritmico, per verificare se esiste una soluzione della congruenza axb (mod m) basta usare l’algoritmo Euclideo delle divisioni successive per calcolare d=mcd(a,m), e poi eseguire una divisione per verificare se db.
La dimostrazione precedente fornisce anche un algoritmo per il calcolo di una soluzione x (se essa esiste cioè se db): basta moltiplicare t (ottenuto dividendo b per d) per z (coefficiente di a nella espressione del mcd(a,m) come combinazione lineare di a,m, calcolato con l’algoritmo Euclideo esteso). Globalmente la complessità dell’algoritmo per il calcolo di una soluzione della congruenza è di ordine non superiore al polinomiale: se ci si riduce (come visto sopra) al caso a,b<m, le lunghezze binarie degli input a,b sono della lunghezza x=L(m) dell’input m, e si ottiene una complessità dell’algoritmo di ordine O(x3).
La soluzione (se esiste) della congruenza axb (mod m) non è unica, ma è possibile determinare tutte le soluzioni, conoscendone una:
Teorema.
Fissato il modulo m>1 e i numeri interi a,b 0, con a>0, e posto d=mcd(a,m):
se esiste una soluzione x0 della congruenza axb (mod m) , tutte e sole le soluzioni sono i numeri interi relativi x1 tali che x1x0 (mod m/d) (ossia i numeri della classe di congruenza [x0]m/d
rappresentata da x0 modulo m/d).
Dimostrazione:
Sia x1 una soluzione della congruenza.
Allora ax1b (mod m), ax0b (mod m), da cui per transitività ax1ax0 (mod m), ax1-ax0=mk con k intero relativo, e dunque (a/d)(x1-x0)=(m/d)k.
Ma per una proprietà già dimostrata, i numeri a/d, m/d sono coprimi (essendo d=mcd(a,m)). Per una proprietà dei numeri coprimi essendo (m/d)(a/d)(x1-x0) si ha (m/d)(x1-x0) ottenendo infine la tesi x1x0 (mod m/d).
Viceversa sia x1 un intero relativo tale che x1x0 (mod m/d).
Allora x1-x0=km/d, con k intero relativo, ax1-ax0=k(a/d)m, ax1ax0 (mod m).
Ma per ipotesi ax0b (mod m), e per transitività anche ax1b (mod m), dunque anche x1 è soluzione della congruenza.
Dai risultati precedenti segue che, fissato il modulo m>1 e i numeri interi a,b 0, con a>0, e posto d=mcd(a,m), e fissata una soluzione x=x0 della congruenza axb (mod m), poiché tutte le soluzioni della stessa congruenza sono gli elementi della classe di congruenza modulo m/d rappresentata da x0, la riduzione modulo m/d di x0 è anch’essa una soluzione ed è l’unica con valore compreso fra 0,1,…,(m/d)-1: tale soluzione è detta soluzione canonica della congruenza.
Esempio:
Risolviamo la congruenza 36x10 (mod 14).
Con l’algoritmo Euclideo, operando n=4 divisioni, otteniamo che d=mcd(36,14)=2, che è divisore di b=14.
Per calcolare i coefficienti interi z, w tali che 2=36z+14w, si costruiscono le successioni si , ti (con i=0,1,2,3,4,5) di cui si è parlato nell’Algoritmo Euclideo esteso, e si trovano alla fine i valori:
z=s4=2, w= -t4= -5.
Una soluzione x della congruenza è data allora da x=tz=10 (dove t=b/d=5).
Tutte le soluzioni sono i numeri della forma 10+k(m/d)=10+7k, con k intero relativo (quindi gli elementi della classe di congruenza rappresentata da 10 modulo m/d=7) e la soluzione canonica è la riduzione 10mod7=3 (l’unica compresa fra 0,1,2,…,6).
Teorema Cinese del Resto.
In un manoscritto cinese del III° sec. a.C. si trova il seguente problema: trovare un intero positivo x che diviso per 3 dia resto 1, diviso per 5 dia resto 2, diviso per 7 dia resto 3.
Nel linguaggio delle congruenze si tratta di trovare un intero positivo che sia soluzione intera del seguente sistema di congruenze di primo grado nell’incognita x:
1 (mod 3) 2 (mod 5) 3 (mod 7) x
x x
Studieremo dunque i sistemi di congruenze di primo grado nell’incognita x in cui il coefficiente della x sia = 1, ossia i sistemi di n congruenze della forma:
1 1
2 2
(mod ) (mod ) ...
...
(mod )
n n
x b m
x b m
x b m
(*)
(dove sono fissati i moduli mi>1 ed i termini noti bi sono supposti non negativi, eventualmente sostituendo ognuno di essi con la sua riduzione modulo mi).
Studiamo prima il caso di 2 congruenze:
Teorema (Teorema Cinese del Resto nel caso di 2 congruenze).
Nel sistema (*), con n=2, se i moduli m1,m2 sono coprimi esiste una soluzione intera x=x0 del sistema e le soluzioni del sistema sono tutti e soli gli interi x1 tali che x1x0 (mod m1m2) (quindi gli elementi della classe di congruenza
x0 m m1 2rappresentata da x0 modulo m1m2).Dimostrazione:
Le soluzioni della prima congruenza del sistema sono tutti gli interi della classe di congruenza rapprresentata da b1 modulo m1, dunque gli interi della forma x=b1+m1y, dove y varia fra gli interi relativi. Imponiamo la condizione che uno di tali interi x sia soluzione anche della seconda congruenza, ottenendo la seguente congruenza di primo grado nell’incognita y:
m1y(b2-b1) (mod m2)
Sappiamo che tale congruenza ha qualche soluzione y=y0 perché mcd(m1,m2)=1 è ovviamente divisore della differenza (b2-b1). Ponendo x0=b1+m1y0 otterremo una soluzione del sistema.
E’ facile verificare che ogni numero intero x1x0 (mod m1m2) è anche soluzione del sistema, in quanto x1x0b1 (mod m1) e x1x0b2 (mod m2).
Viceversa se x1 è soluzione intera del sistema, allora x1x0b1 (mod m1) e x1x0b2 (mod m2), dunque m1,m2 sono divisori di (x1-x0), e per una proprietà dei numeri coprimi anche il prodotto m1m2
è divisore di (x1-x0), ossia x1x0 (mod m1m2).
