Prima di introdurre la nozione di massimo comune divisore (MCD), dobbiamo studiare i concetti di divisibilità fra interi, cioè conoscere le caratteristiche e le proprietà delle divisioni fra numeri interi.

 

Definizione. Siano a e b due interi.   

Si dice che a divide b o che b è divisibile per a (e si indica con a|b ) se esiste ed è unico un intero q tale che b=q×a.

In simboli si ha:

per ogni a,b Î Z ,  a|b se esiste  q Î Z   tale che b=q×a.

 

Questa relazione di divisibilità gode di semplici proprietà:

 

per ogni   a,b,c Î Z, allora

1)      se a|b e b|c, allora a|c;

2)      se a|b e b¹0, allora 1 £ |a| £ |b| ;

3)      1|b e b|b;

4)      se a|b e b|a, allora a = ± b;

5)      se a|1, allora a = ±1;

6)      se  a¹0, allora  a|0;

7)      a|b se e solo se a|(-b) se e solo se (-a)|(b) se e solo se (-a)|(-b);

8)      se a|b e a|c e presi m,n Î Z, allora a|(mb+nc);

l’intero mb+nc si dice combinazione lineare di b e c;

9)      se a|b e a|(b+c), allora a|c.

 

Dimostrazione

 

Esistono anche interi che non sono divisibili per altri interi eccetto che per l’unità e per se stessi, questi numeri vengono chiamati primi:

 

Definizione. Un intero p è primo se p³2 e se i suoi soli divisori sono 1 e p.

 

In particolare, per la proprietà 7), se p è un primo e a un intero allora a|p se a Î {±1, ±p}.

Quindi possiamo anche concludere che se a è un intero positivo, allora a non è un primo se e solo se a=1 o se esistono due interi b,c con b³2, c³2 tali che a=b×c.

 

La scomposizione in fattori primi gode di 3 proprietà fondamentali:

 

Proposizione 1. Ogni intero maggiore o uguale a 2 è primo od è un prodotto di primi.

 

In altre parole, preso un qualunque intero a, esistono p₁,¼,p_r primi (non necessariamente distinti)  tali che

a= p₁×¼×p_r   (r >0)_.   

 

Dimostrazione

                                                           

 

Abbiamo ipotizzato che i fattori della scomposizione non siano necessariamente distinti, infatti si ha che:

 

Proposizione 2. Sia a³2 un intero. Allora esistono dei primi p₁,¼,p_r con p₁<p₂<…<p_r degli interi positivi m₁,…,m_r tali che

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

dove p₁,¼,p_r  sono chiamati fattori primi di a, mentre m_i è l’esponente di p_i per i=1,…r di a.

In seguito proveremo che questa scomposizione è unica.

 

Una conseguenza fondamentale di questa proposizione è che ogni intero maggiore di 2 è divisibile per almeno un primo. Questa osservazione ci permette di dimostrare il seguente teorema:

 

Teorema 3. Esiste un numero infinito di primi.

 

Dimostrazione