Ora sappiamo che esistono primi divisibili solo per 1 e per se stessi e interi scomponibili in fattori primi. Possiamo quindi studiare le relazioni che esistono fra i divisori di due numeri:

 

Definizione. Siano a e b due interi non entrambi nulli.

Chiameremo massimo comun divisore di a e b, e lo denoteremo con il simbolo MCD, il più grande intero positivo che divide sia a che b.

In simboli si ha:

"a,b Î Z,   MCD(a,b)=d, dÎ Z Û

i)                    d|a e d|b,

ii)                   preso cÎZ, se c|a e c|b Þ c|d.

 

In particolare, presi a,b Î Z, se MCD(a,b)=1, allora a e b sono detti relativamente primi, cioè non esiste un intero che sia divisore di entrambi eccetto l’unità.

 

Possiamo osservare che se consideriamo due interi nulli, cioè se a=b=0, non esiste il MCD(a,b), poiché ogni numero intero divide entrambi, mentre se prendiamo due numeri tali che p sia primo e a un intero qualsiasi, si ha che:

-         MCD(p,a) = p,   se p|a,

-         MCD(p,a) = 1    altrimenti.

 

La definizione di massimo comun denominatore può essere estesa anche a n numeri:

 

Definizione. Siano a₁,…, a_n interi non tutti nulli.

Allora il MCD(a₁,…, a_n) è il più grande intero positivo che divide ogni termine, in simboli:

presi a₁,…, a_n  Î Z, MCD(a₁,…, a_n) = d Û

1)  d|a_i               "i=1,…,n;

2)  preso cÎZ, se c|a_i   "i=1,…,n, allora c|d.

 

Analogamente se MCD(a₁,…, a_n) = 1, allora gli n termini si dicono relativamente primi, cioè l’unico fattore che divide tutti gli n interi è l’unità.

Il seguente lemma risulterà di fondamentale importanza per il proseguo della trattazione:

 

Lemma di divisione.

Siano a,b due interi con a ¹ 0.

Allora sono univocamente determinati due interi q,r tali che:

i)                    b = q×a +r,

ii)                   0 £ r < |a|,

dove q è il quoziente della divisione e r è il resto della divisione fra a e b.

 

Dimostrazione

 

Come conseguenza di questo lemma, possiamo studiare un teorema fondamentale per la nostra trattazione che dice che il MCD di due interi a e b è una combinazione lineare di a e di b:

 

Teorema. Dati a,b Î Z non entrambi nulli, esistono due interi s,t ÎZ tali che

MCD(a,b) = sa + tb.

 

Dimostrazione

 

Osservazioni.

I coefficienti s e t della combinazione lineare non sono unici, infatti presi s’=s+b e t’=t-a si ha

s’a+t’b = (s+b)a+(t-a)b = sa+ba+tb-ab = sa+tb.

Inoltre si deduce che un numero divide sia a che b se e solo se divide anche MCD(a,b).

 

Ora indichiamo quattro corollari che sfruttano questo risultato:

 

Corollario 1)      Due interi a e b sono primi fra loro se e solo se esistono due interi s,t tali che

sa+tb = 1.

Dimostrazione

Corollario 2)      Se un intero a divide un prodotto b×c e a è relativamente primo con b, allora a divide c.

In simboli:

se a|bc e MCD(a,b)=1, allora a|c.

Dimostrazione

Corollario 3)      Se un primo p divide un prodotto di n interi a₁,…,a_n, allora p divide almeno un fattore a_i , per i=1,…,n.

(Questo corollario ci permetterà di dimostrare l’unicità della scomposizione in fattori primi).

Dimostrazione

Corollario 4)      Se m|a e n|a e se MCD(m,n)=1, allora m×n = a.

Dimostrazione

Ora abbiamo tutte le conoscenze necessarie per dimostrare che la scomposizione in fattori primi è unica. Esistono diversi procedimenti per ottenere questo risultato e qui riportiamo la soluzione che a nostro avviso è più trasparente:

 

Teorema. Ogni intero maggiore di 1 ha un’unica scomposizione in fattori primi. In simboli:

per ogni aÎZ, a>1, esistono e sono unici p₁,…,p_r primi e m₁,…,m_r naturali tali che

a= p₁^m₁× p₂^m₂×…× p_r^m_r,    con p₁<p₂<…<p_r.

Dimostrazione

Ora tutte queste nozioni sono propedeutiche per studiare l’algoritmo euclideo, un procedimento quasi “meccanico” che consiste in una serie di divisioni successive che consentono di calcolare il massimo comun  divisore di due numeri a,b e gli interi s,t tali che

MCD(a,b) = d  e  d=sa+tb,

senza scomporre a e b in fattori primi.

 

 

Prendiamo a,b interi con a,b>0 e supponiamo 0<a<b.

Dividiamo b per a, avremo che:

b = q₁×a+r₁,   con 0 £ r₁<a.

Osserviamo che:

i)                    se r₁=0, allora b = q₁×a e abbiamo già che MCD(a,b)=a;

ii)                   altrimenti, preso un intero positivo d

1)     se d divide sia a che b, allora dividerà anche r₁ in quanto combinazione lineare di a e b;

2)     viceversa, se d divide a e r₁, dividerà anche b per la stessa proprietà sopra.

Quindi possiamo concludere che

MCD(a,b) = MCD(a,r₁),

con il vantaggio che r₁<a<b.

Ora ripetiamo lo stesso procedimento sostituendo al posto di a e b i nuovi valori a e r₁ con r₁<a:

a = q₂×r₁+r₂,   con 0 £ r₂<r₁

dove

i)                    se r₂=0, si ha che r₂|a, quindi MCD(a,b) = MCD(a,r₁) = r₂;

ii)                   altrimenti, si ripetono le stesse conclusioni giungendo a definire che MCD(a,b)=MCD(a,r₁)=MCD(r₁,r₂).

 

Continuiamo a costruire queste successioni di resto sino ad arrivare all’i-esima iterazione dove

r_i-1 = q_i+1×r_i+r_i+1,   con 0 £ r_i+1<r_i

e avremo che

i)                    se r_i=0, allora MCD(a,b) = r_i-1;

ii)                   altrimenti, continuiamo il procedimento.

 

Poiché gli r_i sono interi non negativi e la successione di resti è decrescente, ad un certo punto ci dovremo fermare, cioè esisterà un r_n diverso da zero tale che r_n+1=0, allora il nostro MCD(a,b) sarà uguale all’ultimo resto diverso da zero della catena di divisioni.

 

Questo procedimento è vantaggioso perché non dobbiamo scomporre in fattori primi e si utilizzano divisioni sempre più facili.

Proviamo ora a ricostruire s,t procedendo a ritroso nell’algoritmo euclideo:

presi MCD(a,b) = r_n  e  sa+tb = r_n, possiamo scrivere

r_n = r_n-2 - q_n×r_n-1,

e andiamo a sostituire il valore di r_n-1 che si ricava dall’uguaglianza r_n-3 = q_n-1×r_n-2 + r_n-1:

r_n = r_n-2 - q_n× (r_n-3 - q_n-1×r_n-2) = (1+q_nq_n-1) r_n-2 - q_n× r_n-3.

Ora sostituiamo in questa equazione il valore di r_n-2 che si ottiene da r_n-4 = q_n-2×r_n-3 + r_n-2 e avremo r_n come espressione in r_n-3 e r_n-4, quindi andremo a sostituire r_n-3 e continueremo questo procedimento fino ad ottenere r_n come combinazione lineare dei soli a e b.

 

• Esempi

• Esercizi