Page 99 - Capire la matematica

Approfondimento: Geometricamente si può fare un esempio con le piastrelle: il MCD
rappresenta il lato della piastrella quadrata più grande con cui si può rivestire una parete
rettangolare lunga rispettivamente ad es. 18 e 84, senza dover tagliare nessuna pia-
strella (6x6) in quanto il MCD (18,84) = 6.

Per calcolare il MCD fra dei numeri bisogna innanzitutto scomporre questi numeri:

es. 18 = 2x3x3 e 84 = 2x2x3x7

Confrontandoli si vede che 2 e 3 sono i più alti valori comuni che li compongono. In con-
clusione 2x3=6 è il fattore più grande che li divide entrambi.

Questo procedimento va bene per valori abbastanza piccoli, ma per valori molto grandi

esiste un algoritmo fornito da Euclide che ci semplifica la vita.

Si inizia dividendo il valore più grande per quello più piccolo.

Esempio. 84/18. Si ottiene 4 con resto di 12. Ora si divide il numero più piccolo 18 per il
resto ottenuto 18/12= 1 con resto 6. Ora si divide 12/6 che da resto = 0. Quindi 6 è il
nostro M.C.D.

Il MCD può essere usato per risolvere le equazioni che ammettono come soluzioni dei
numeri interi (Equazioni diofantee che prendono il nome dal matematico Diofanto di
Alessandria).

Identità di Bezout: Se d = (a; b) è il MCD di a e b, allora esistono due interi m ed n tali che
d = ma + nb.

Esercizio 1: Determinare il MCD di 721 e 448 ed esprimerlo nella forma 721m + 448n
con m, n ∈ Z: Al massimo quante divisioni si dovranno fare per determinare (721, 448)?

Soluzione: Facendo i calcoli si ottiene (721, 448) = 7 e 7 = 23∙721 - 37∙448.

Siccome l’algoritmo termina in un numero intero di passi minore o uguale a 2 log2448,
essendo log2448 = 8.807 … , l’algoritmo termina sicuramente in 17 passi.

Esempio: L’equazione 3x - 9 = 0 ha soluzione x = 3. L’equazione 3x - 8 = 0 non ha soluzioni
in Z.

Esercizio 2: Risolvere in Z l’equazione 12x + 39y = 15.

Soluzione: Si ha d = (12, 39) = 3 che si può scrivere nella forma 3 = (-3)(12) + (1)(39), da
cui, moltiplicando per 5, si ottiene l’identità 12(-15)+ (39)(5) = 15, che fornisce la solu-
zione particolare (x0, y0) = (-15, 5).

La soluzione generale è quindi (x1, y1) con x1 = -15+13k, y1 = 5-4k, ∀k ∈ Z.

- 99 -