Gli "Elementi" di Euclide

LIBRO VII

 

PROPOSIZIONE 3

Prop.3: Trovare la massima misura comune di tre numeri dati non primi tra loro
Dimostrazione
 

Siano A, B, C i tre numeri dati non primi tra loro: si deve pertanto trovare la massima misura comune di A, B, C.

Si prenda la massima misura comune, D, dei due numeri A e B (Prop.7-2). Poi o D misura, o non misura, C. In primo luogo lo misuri. Ma misuri anche A e B, pertanto D misura A, B, e C. D è quindi la misura comune di A, B, C. Dico che è anche la massima.

Se D non la massima misura comune di A, B, C, allora un certo numero E, maggiore di D, misura i numeri A, B, C. Poiché dunque E misura A, B, C, misura quindi anche A e B. Pertanto misura anche la massima misura comune di A e B. Ma la massima misura comune di A e B è D, pertanto E misura D, il maggiore il minore, il che è impossibile. Non si dà quindi il caso che un certo numero, che è maggiore di D, misuri i numeri A, B, e C. D è quindi la massima misura comune di A, B, C.

D non misuri ora C: dico che C e D non sono primi tra loro.

Poiché A, B, C non sono primi tra loro, allora un certo numero li misura. Ora, quello che misura A, B, C misura anche A e B, e quindi misura D, la massima misura comune di A e B (Prop.7-2-Cor). Ma misura anche C, pertanto un certo numero misura i numeri D e C. D e C non sono quindi primi tra loro.

Si prenda quindi la loro massima misura comune, E (Prop.7-2). Poiché quindi E misura D, e D misura A e B, allora E misura anche A e B. Ma misura anche C, pertanto E misura A, B, C. E è quindi la misura comune di A, B, C.

Dico ora che è anche la massima. Se E non è la massima misura comune di A, B, C, allora un certo numero F, maggiore di E, misura i numeri A, B, C. Ora, poiché F misura A, B, e C, misura anche A e B, misura quindi la massima misura comune di A e B. Ma la massima misura comune di A e B è D, pertanto F misura D (Prop.7-2-Cor).

E misura anche C; F misura pertanto D e C. Misura quindi la massima misura comune di D e C. Ma la massima misura comune di D e C è E, F misura quindi E, il maggiore il minore, il che è impossibile (Prop.7-2-Cor). Non si dà quindi il caso che un certo numero che sia maggiore di E misuri i numeri A, B, C.

  Pertanto nessun numero che è maggiore di CF misura i numeri AB e CD. CF è quindi la massima misura comune di AB e CD.
   
Corollario
  Se un numero misura due numeri, allora misura anche la loro massima misura comune

.

La costruzione con Geogebra:
  1. strumento Retta: disegna tre rette sulle quali collocare i tre segmenti
  2. strumento Segmento: disegna il segmento AB su una retta e CD su un'altra retta
  3. strumento Circonferenza di dato raggio: traccia le circonferenze di centro B e raggio CD tante volte quante CD è contenuto in AB. L'ultima intersezione sia E
  4. strumento Segmento: disegna il segmento AE
  5. strumento Circonferenza di dato raggio: traccia le circonferenze di centro D e raggio AE tante volte quante AE è contenuto in CD. Sia F l'ultima intersezione.
  6. strumento Segmento: disegna il segmento CF
  7. strumento Segmento: disegna il segmento G sulla terza retta

 

In questa proposizione viene utilizzato ancora l'algoritmo precedente per calcolare il massimo comun divisore (MCD) di due numeri, che non sono primi tra loro. In quest'ultimo caso il MCD esiste e vale 1.

Invece di sottrarre ripetutamente è possibile dividere in successioni i numeri.

Ad esempio, se si deve calcolare il MCD(28,36) si può procedere così: dopo aver individuato il numero maggiore:

- divido il maggiore per il minore, cioè, 36:28=1 con resto 8

- divido il precedente divisore con il resto ottenuto: 28:8=3 con resto 4

- itero questo procedimento: 8:4=2 con resto 0.

Quando il resto è 0, la procedura si arresta e 2, l'ultimo divisore, è il divisore comune.

Questo algoritmo può essere facilmente tradotto in linguaggio informatico, sfruttando l'operazione tra naturali mod, che restituisce come risultato il resto della divisione.

Questa proposizione è utilizzata nella successive due dimostrazioni.