è anch’essa una soluzione ed è l’unica con valore compreso fra 0,1,

(1)

Lezione dl 31 marzo 2008

Dai risultati precedenti segue che, dati i numeri naturali a,b,m con m>1 e fissata (se d=mcd(a,m)b) una soluzione x=x

0

della congruenza axb (mod m), poiché tutte le soluzioni della stessa congruenza sono gli elementi della classe di congruenza modulo m/d rappresentata da x

0

, la riduzione modulo m/d di x

0

è 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 36x10 (mod 14).

Con l’algoritmo Euclideo, operando n=4 divisioni, otteniamo che d=mcd(36,14)=2, divisore di b=14.

Per calcolare i coefficienti interi z, w tali che 2=36z+10w, si costruiscono le successioni s

i

, t

i

(con i=0,1,2,3,4,5) di cui si è parlato nell’Algoritmo Euclideo esteso, e si trovano i valori:

z=s

4

=2, w= -t

4

= 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 è 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 tale che xmod3=1, xmod5=2, xmod7=3, e quindi una soluzione intera positiva x del seguente sistema di congruenze di primo grado nell’incognita x:

 

 





7) (mod 3 x

5) (mod 2 x

3) (mod 1 x

Studieremo dunque i sistemi di congruenze di primo grado nell’incognita x in cui il coefficiente della x sia = 1:

 















) m (mod b x ...

...

) m (mod b x

n n

2 2

1 1

(*)

(dove sono fissati i termini noti b

i

interi >0, i moduli m

i

interi >1 e il numero n>1 delle congruenze).

Studiamo prima il caso di 2 congruenze:

(2)

Teorema (Teorema Cinese del Resto nel caso di 2 congruenze).

Nel sistema (*), con n=2, se i moduli m

1

,m

2

sono coprimi esiste una soluzione intera x=x

0

del sistema e inoltre le soluzioni intere x

1

del sistema sono tutti e soli i numeri x

1

x

0

(mod m

1

m

2

) (quindi gli elementi della classe di congruenza   x

₀ _m₁_m₂

rappresentata da x

0

modulo m

1

m

2

).

Dimostrazione:

Le soluzioni della prima congruenza del sistema sono tutti gli interi della classe di congruenza rapprresentata da b

1

modulo m

1

, dunque gli interi della forma x=b

1

+m

1

y, 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:

m

1

y(b

2

-b

1

) (mod m

2

)

Sappiamo che tale congruenza ha qualche soluzione y=y

0

perché mcd(m

1

,m

2

)=1 è ovviamente divisore della differenza (b

2

-b

1

). Ponendo x

0

=b

1

+m

1

y

0

otterremo una soluzione del sistema.

E’ facile verificare che ogni numero intero x

1

x

0

(mod m

1

m

2

) è anche soluzione del sistema, in quanto x

1

x

0

b

1

(mod m

1

) e x

1

x

0

b

2

(mod m

2

).

Viceversa se x

1

è soluzione intera del sistema, allora x

1

x

0

b

1

(mod m

1

) e x

1

x

0

b

2

(mod m

2

), dunque m

1

,m

2

sono divisori di (x

1

-x

0

), e per una proprietà dei numeri coprimi anche il prodotto m

1

m

2

è divisore di (x

1

-x

0

), ossia x

1

x

0

(mod m

1

m

2

).

Esempio.

Risolviamo il sistema formato dalle prime 2 congruenze del problema del manoscritto cinese:

 





5) (mod 2 x

3) (mod 1 x

Le soluzioni della prima congruenza sono della forma x=1+3y, con y intero, e imponendo che siano soluzioni anche della seconda si ottiene la congruenza di primo grado in y:

3y1 (mod 5)

Una soluzione è y=ts, dove t si ottiene dividendo il termine noto 1 per il mcd(3,5)=1(quindi t=1), ed s è il coefficiente di 3 nella rappresentazione di 1=mcd(3,5) come combinazione lineare di 3 e 5:

quindi da 1=32+5(-1) segue s=2. Si ha y=2, e una soluzione del sistema è allora x=1+3y=7: tutte le soluzioni del sistema sono i numeri della classe di congruenza [7]

15

rappresentata da 7 modulo 15, dunque tutti gli interi della forma 7+15k, con k intero relativo (per esempio i numeri -8, 22, 37 etc…).

Nel caso generale di n congruenze si ottiene un risultato analogo a quello del caso n=2:

Teorema (Teorema Cinese del Resto nel caso generale di n congruenze).

Nel sistema (*), con n>1 qualunque, se i moduli m

1

sono a due a due coprimi esiste una soluzione intera x=x

0

del sistema e inoltre le soluzioni intere x

1

del sistema sono tutti e soli i numeri x

1

x

0

(mod m

1

m

2

…m

n

) (quindi gli elementi della classe di congruenza  

n 2 1m ...m 0 m

x rappresentata da x

0

modulo m

1

m

2

…m

n

).

Dimostrazione:

Per induzione (I

^a

forma) su n, con base n=2.

Per n=2 la tesi segue dal Teorema precedente.

(3)

Supponiamo il Teorema vero per n e dimostriamolo per n+1.

Dato il sistema di n+1 congruenze:

 

















 (mod m ) b

x ...

...

) m (mod b x

1 n 1

n

2 2

1 1

Per induzione esiste una soluzione intera z del sistema formato dalle prime n congruenze, e inoltre tutte e sole le soluzioni di tale sistema sono z (mod m

1

m

2

…m

n

). Dunque il sistema di n+1 congruenze dato equivale al sistema di 2 congruenze:

 







 (mod m ) b

x

) ...m m m (mod z x

1 n 1

n

n 2 1

Notiamo che i moduli delle 2 congruenze sono coprimi: se per assurdo d=mcd(m

1

m

2

…m

n

,m

n+1

)>1, considerato un divisore primo p di d sarebbe p divisore del prodotto m

1

m

2

…m

n

(quindi p divisore di qualche m

i

con i=1,2,…,n) e di m

n+1

, contro l’ipotesi che m

i

,m

n+1

sono coprimi.

Per il Teorema precedente (il caso di 2 congruenze) si ha la tesi per n+1: il sistema ha soluzione x

0

e le soluzioni sono tutti e soli gli interi x

0

(mod m

1

m

2

…m

n+1

).

Fissata una soluzione x=x

0

del sistema (*), poiché tutte le soluzioni del sistema sono gli elementi della classe di congruenza modulo m

1

m

2

…m

n

rappresentata da x

0

, la riduzione modulo m

1

m

2

…m

n

di x

0

è anch’essa una soluzione ed è l’unica con valore compreso fra 0,1,…, m

1

m

2

…m

n

-1: tale soluzione è detta soluzione canonica del sistema (ovviamente essa è anche la minima soluzione 0 del sistema)

Esempio.

Risolviamo il sistema formato dalle 3 congruenze del problema del manoscritto cinese:

 

 





7) (mod 3 x

5) (mod 2 x

3) (mod 1 x

Abbiamo già risolto il sistema formato dalle prime 2 congruenze, le cui soluzioni sono 7 (mod 15).

Il sistema dato equivale allora al sistema di 2 congruenze:

 





7) (mod 3 x

15)

(mod

7 x

(4)

Le soluzioni della prima congruenza sono della forma x=7+15y con y intero, e imponendo che siano soluzioni della seconda si ottiene la congruenza in y:

15y -4 (mod 7)

una cui soluzione è y=rs , dove r=-4/mcd(15,7)= -4, s è il coefficiente di 15 nella rappresentazione di 1=mcd(15,7) come combinazione lineare di 15, 7 (si ha 1=151+7(-2), quindi s=1), e si ha y=-4.