I riassunti , gli appunti i testi contenuti nel nostro sito sono messi a disposizione gratuitamente con finalità illustrative didattiche, scientifiche, a carattere sociale, civile e culturale a tutti i possibili interessati secondo il concetto del fair use e con l' obiettivo del rispetto della direttiva europea 2001/29/CE e dell' art. 70 della legge 633/1941 sul diritto d'autore
Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).
Teoria dei numeri e Crittografia
Congruenze aritmetiche.
Ricordiamo la teoria delle congruenze aritmetiche.
La nozione di divisore (e simmetricamente quella di multiplo) si estende facilmente dall’insieme N dei numeri naturali all’insieme Z dei numeri interi relativi: dati gli interi relativi a,bÎZ si dice che a è divisore di b (o che b è multiplo di a) e si scrive a½b, se esiste un intero relativo cÎZ tale che ac=b.
Fissato un intero relativo m (detto modulo), e dati i numeri interi relativi a,b, diremo che a è congruo b modulo m (e scriveremo aºb (mod m)) se mï(a-b).
In questo modo definiamo nell’insieme Z degli interi relativi una relazione, detta appunto congruenza modulo m, che è una relazione di equivalenza (come si dimostra facilmente).
Poiché è facile verificare che la congruenza modulo m coincide con la congruenza modulo –m, possiamo limitarci a studiare il caso di m³0.
Poiché inoltre sono banali i casi m=0 (la congruenza modulo 0 non è altro che la relazione di eguaglianza) ed m=1 (nella congruenza modulo 1 tutti gli interi sono congrui fra loro) ci limiteremo a studiare il caso m>1.
Per ogni aÎZ si può costruire la classe di equivalenza rappresentata da a (detta classe di congruenza modulo m rappresentata da a):
[a]m = { xÎZ / xºa (mod m) } = { xÎZ / x-a=km, con kÎZ } = { xÎZ / x=a+km, con kÎZ }
(se non vi è possibilità di equivoco sul modulo m, useremo semplicemente il simbolo [a])
Per la teoria generale delle relazioni di equivalenza, dati a,bÎZ si ha [a]=[b]Û aºb (mod m), e inoltre le classi di congruenza modulo m formano una partizione dell’insieme Z .
Teorema.
Fissato il modulo m>1, le classi di congruenza modulo m distinte sono tutte e sole le seguenti:
[0], [1], ……, [m-1] (*)
Dimostrazione:
Le classi (*) sono distinte: se per assurdo fosse [a]=[b] con 0£b<a<n, si avrebbe aºb (mod m), dunque 0<a-b<m sarebbe un multiplo di m (contraddizione).
Per ogni aÎZ la classe di congruenza [a] coincide con una delle classi (*): infatti se a>0 allora, dividendo a per m con quoziente q e resto r si ha a=mq+r , a-r=mq, aºr (mod m), [a]=[r], con r compreso fra i valori 0,1,…,m-1; se invece a<0 allora, dividendo (-a) per m con quoziente q e resto r si ha -a=mq+r , a-(m-r)=m(-q-1), aºm-r (mod m), [a]=[m-r], con m-r compreso fra 1,…,m-1 (se r>0) oppure (se r=0) con [a]=[m]=[0].
Poiché 0,1,…,m-1 sono i possibili resti delle divisioni per m, le classi di congruenza modulo m sono anche dette classi resto modulo m, e il loro insieme è indicato con Zm : per il Teorema precedente si ha Zm= { [0], [1], ……, [m-1] }, e la cardinalità di Zm è uguale al modulo m.
Nella dimostrazione del Teorema, per ogni intero relativo aÎZ si è costruito un (unico) intero t compreso fra i valori 0,1,…,m-1 tale che [a]=[t] (o equivalentemente tale che aºt (mod m)): tale t è detto riduzione modulo m dell’intero a ed è indicato con amodm.
Se in particolare a è un numero naturale, un algoritmo per il calcolo della sua riduzione modulo m è indicato nella dimostrazione del Teorema: basta dividere a per m e considerare il resto r=amodm (algoritmo, come sappiamo, di complessità quadratica).
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:
aºb (mod m), cºd (mod m)
seguono sempre:
a+cºb+d (mod m) (compatibilità della congruenza rispetto alla somma)
acºbd (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), mïac-bd.
In particolare, comunque fissato un intero relativo y , da aºb (mod m) seguono sempre:
a+yºb+y (mod m)
ayºby (mod m)
(basta ricordare che per la proprietà riflessiva si ha yºy (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 axºb (mod m) . Diremo anche che tali valori x sono le soluzioni della congruenza axºb (mod m) di primo grado nell’incognita x.
Sostituendo eventualmente a con amodm (la sua riduzione modulo m) otteniamo una congruenza equivalente (per la compatibilità della congruenza rispetto alla somma e al prodotto), dunque possiamo ricondurci sempre al caso in cui a³ 0 (ed anche a<m). Per evitare casi banali supporremo anche a>0 (se a=0 ovviamente la congruenza ha per soluzione ogni intero relativo se bº0 (mod m), o in caso contrario non ha soluzioni).
Vediamo quando una soluzione della congruenza di primo grado esiste:
Teorema.
Fissato il modulo m>1 e i numeri interi relativi a,b, con a>0, e posto d=mcd(a,m):
esiste una soluzione x della congruenza axºb (mod m) Û d é divisore di b.
Dimostrazione:
(Þ): Se axºb (mod m), si ha ax-b=km, con kÎZ, da cui, essendo dïa, dïm, ovviamente dïb.
(Ü): Se dïb, posto dt=b, con tÎZ, e posto d=mcd(a,m)=az+mw, con z,wÎZ, si ottiene b=dt=azt+mwt, da cui aztºb (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 axºb (mod m) basta usare l’algoritmo Euclideo delle divisioni successive per calcolare d=mcd(a,m), e poi eseguire una divisione per verificare se dïb (complessità totale di ordine cubico).
La dimostrazione precedente fornisce anche un algoritmo per il calcolo di una soluzione x (se essa esiste cioè se dïb): 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): anche la complessità dell’algoritmo per il calcolo di una soluzione della congruenza è dunque di ordine cubico.
La soluzione (se esiste) della congruenza axºb (mod m) non è unica, ma è possibile determinare tutte le soluzioni, conoscendone una:
Teorema.
Fissato il modulo m>1 e i numeri interi relativi a,b, con a>0, e posto d=mcd(a,m):
se esiste una soluzione x0 della congruenza axºb (mod m) , tutte e sole le soluzioni sono i numeri interi relativi x1 tali che x1ºx0 (mod m/d) (ossia i numeri della classe di congruenza [x0]m/drappresentata da x0 modulo m/d).
Dimostrazione:
Sia x1 una soluzione della congruenza.
Allora ax1ºb (mod m), ax0ºb (mod m), da cui per transitività ax1ºax0 (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 x1ºx0 (mod m/d).
Viceversa sia x1 un intero relativo tale che x1ºx0(mod m/d).
Allora x1-x0=km/d, con k intero relativo, ax1-ax0=k(a/d)m, ax1ºax0 (mod m).
Ma per ipotesi ax0ºb (mod m), e per transitività anche ax1ºb (mod m), dunque anche x1 è soluzione della congruenza.
Dai risultati precedenti segue che, fissato il modulo m>1 e i numeri interi relativi a,b, con a>0, posto d=mcd(a,m), e fissata una soluzione x=x0della congruenza axºb (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 36xº10 (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:
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:
(*)
(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 x1ºx0 (mod m1m2) (quindi gli elementi della classe di congruenza 
rappresentata 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 x1ºx0 (mod m1m2) è anche soluzione del sistema, in quanto x1ºx0ºb1(mod m1) e x1ºx0ºb2(mod m2).
Viceversa se x1 è soluzione intera del sistema, allora x1ºx0ºb1 (mod m1) e x1ºx0ºb2 (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 x1ºx0 (mod m1m2).
Esempio.
Risolviamo il sistema formato dalle prime 2 congruenze del problema del manoscritto cinese:
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 m1 sono a due a due coprimi esiste una soluzione intera x=x0 del sistema e le soluzioni del sistema sono tutti e soli gli interi x1 tali che x1ºx (mod m1m2…mn) (quindi gli elementi della classe di congruenza 
rappresentata da x0 modulo m1m2…mn).
Dimostrazione:
Per induzione (Ia forma) su n, con base n=2.
Per n=2 la tesi segue dal Teorema precedente.
Supponiamo il Teorema vero per n e dimostriamolo per n+1.
Dato il sistema di n+1 congruenze:
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 m1m2…mn). Dunque il sistema di n+1 congruenze dato equivale al sistema di 2 congruenze:
Notiamo che i moduli delle 2 congruenze sono coprimi: se per assurdo d=mcd(m1m2…mn,mn+1)>1, considerato un divisore primo p di d sarebbe p divisore del prodotto m1m2…mn(quindi p divisore di qualche mi con i=1,2,…,n) e di mn+1, contro l’ipotesi che mi,mn+1 sono coprimi.
Per il Teorema precedente (il caso di 2 congruenze) si ha la tesi per n+1: il sistema ha soluzione x0 e le soluzioni sono tutti e soli gli interi ºx0 (mod m1m2…mn+1).
Fissata una soluzione x=x0 del sistema (*), poiché tutte le soluzioni del sistema sono gli elementi della classe di congruenza modulo m1m2…mn rappresentata da x0, la riduzione modulo m1m2…mn di x0 è anch’essa una soluzione ed è l’unica con valore compreso fra 0,1,…, m1m2…mn-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:
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:
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).
Sostituendo -4 con la sua riduzione modulo 7, si ottiene la congruenza equivalente:
15yº 3 (mod 7)
una cui soluzione è y=rs , dove r=3/mcd(15,7)= 3, 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=3.
Una soluzione del sistema iniziale è allora x=7+15×3= 52.
La soluzione canonica del sistema è la riduzione 52mod(3×5×7)=52mod105=52 (è l’unica compresa fra 0,1,…,104). Quindi x=52 è la soluzione (minima fra quelle positive) del problema del manoscritto cinese.
Fonte: http://math.unipa.it/~difranco/documents/Lezione2011.11.02_000.doc
Sito web da visitare: http://math.unipa.it
Autore del testo: non indicato nel documento di origine
Il testo è di proprietà dei rispettivi autori che ringraziamo per l'opportunità che ci danno di far conoscere gratuitamente i loro testi per finalità illustrative e didattiche. Se siete gli autori del testo e siete interessati a richiedere la rimozione del testo o l'inserimento di altre informazioni inviateci un e-mail dopo le opportune verifiche soddisferemo la vostra richiesta nel più breve tempo possibile.
I riassunti , gli appunti i testi contenuti nel nostro sito sono messi a disposizione gratuitamente con finalità illustrative didattiche, scientifiche, a carattere sociale, civile e culturale a tutti i possibili interessati secondo il concetto del fair use e con l' obiettivo del rispetto della direttiva europea 2001/29/CE e dell' art. 70 della legge 633/1941 sul diritto d'autore
Le informazioni di medicina e salute contenute nel sito sono di natura generale ed a scopo puramente divulgativo e per questo motivo non possono sostituire in alcun caso il consiglio di un medico (ovvero un soggetto abilitato legalmente alla professione).
"Ciò che sappiamo è una goccia, ciò che ignoriamo un oceano!" Isaac Newton. Essendo impossibile tenere a mente l'enorme quantità di informazioni, l'importante è sapere dove ritrovare l'informazione quando questa serve. U. Eco
www.riassuntini.com dove ritrovare l'informazione quando questa serve