[Risolto] Matematica

Il metodo che io preferisco è quello delle divisioni successive: è un algoritmo classico (inventato da Euclide circa 2300 anni addietro) ed è ancora oggi assai più efficiente della scomposizione in fattori primi.
La spiegazione è un po' lunghina la prima volta, ma una volta capita fa risparmiare una quantità di operazioni (divisioni e moltiplicazioni).
Ti mostro come si applica ai termini di una frazione dell'esercizio #166 (quelli della foto piccola non riesco a leggerli; sono un 81-enne presbite, a bassa acuità!).
Una volta che hai capito il metodo ne riesci a calcolare uno ogni tre minuti.
------------------------------
A) Si divide l'intero maggiore per il minore, producendo un quoziente Q e un resto R
* maggiore = Q*minore + R
* 630 = 1*490 + 140
* 780 = 2*325 + 130
* 306 = 1*255 + 51
* 306 = 1*255 + 51
* 294 = 1*252 + 42
------------------------------
B) Se il resto è positivo si reitera la divisione usando l'attuale divisore come dividendo e l'attuale resto come divisore.
Si continua a iterare fino a trovare R = 0: ciò vuol dire che il dividendo è un multiplo del divisore e quindi che l'attuale divisore è il MCD dei due interi originali.
Per la riduzione ai minimi termini bastano poi due divisioni per il MCD.
Uso la scrittura
* divmod(N, D) = (Q, R)
per indicare
* N = Q*D + R
------------------------------
B1) ESEMPIO
divmod(630, 490) = (1, 140)
divmod(490, 140) = (3, 70)
divmod(140, 70) = (2, 0) ≡ MCD(630, 490) = 70
* 490/630 = (490/70)/(630/70) = 7/9
CINQUE DIVISIONI con l'algoritmo di Euclide.
---------------
B2) CONFRONTO
Invece, con la scomposizione in fattori primi, si hanno
* 630 = 2*(3^2)*5*7 [4 divisioni]
* 490 = 2*5*7^2 [3 divisioni]
* MCD(630, 490) = 2*5*7 = 70 [2 moltiplicazioni]
NOVE OPERAZIONI invece di cinque.
Il risparmio diventa tanto maggiore quanto più crescono i numeri.