14 - LE BASI TEORICHE DELL’ALGORITMO DI EUCLIDE PER IL CALCOLO DEL M.C.D.

Siano  due interi, e sia  un loro divisore comune.

Dico che  è pure divisore del resto che si ottiene effettuando la divisione intera .

Infatti:

la divisione intera  produce

un “quoziente intero”  e un resto ,

legati dalla relazione .

Ma se  è un divisore comune per  e ,

allora  è contenuto

un “numero esatto” di volte sia in  che in ,

e ciò implica che sia contenuto

un numero esatto di volte pure in , perché

 Per capire meglio, vediamo un esempio specifico.

Siano  due numeri interi, e sia  un intero, che risulti divisore comune

a uno di questi due numeri (ad esempio,  ) e al resto della divisione intera .

Dico che  è pure divisore dell’altro numero.

La giustificazione generale

è analoga alla precedente.

 Per capire meglio, vediamo anche qui un esempio specifico.

Ricapitoliamo.

Ci sono tre interi in gioco, che sono .

Abbiamo scoperto che se  è divisore di DUE fra i tre interi considerati,

allora sarà necessariamente divisore anche del terzo.

Dal discorso fatto, ci interessa trarre quanto segue.

Detti  due interi, e detto  il resto della divisione intera , allora:

·       se  è divisore comune per , allora  è pure divisore comune per  

·       se  è divisore comune per , allora  è pure divisore comune per  

per cui

l’insieme dei divisori comuni della coppia  

coincide con l’insieme dei divisori comuni della coppia  

quindi si ha pure

Il vantaggio di tutto ciò sta nel fatto che

il calcolo di  

può essere sostituito da quello di  

che è più facile perché più piccoli sono i numeri in gioco.

E’ sulla base di queste considerazioni che “funziona”

l’ ALGORITMO DI EUCLIDE per la ricerca del M.C.D.

di cui ci siamo occupati alle pagine precedenti.