Algoritmo di Euclide

[dr00ster]

Salve a tutti! Questo è il mio primo topic, spero di aver scritto nella sezione giusta...

Mi sono imbattuto poco fa nell'algoritmo di Euclide per il calcolo dell'MCD fra due numeri.
Chiamando il primo numero a e il secondo b (a>b), l'MCD tra i due numeri è uguale all'MCD tra b e a mod b.
Si continua per ricorsione in questa maniera fino a trovare come secondo termine 0. In tal caso l'MCD cercato è proprio il primo termine.

Scusatemi se la mia spiegazione non è molto esaustiva, ma non mi è chiara la dimostrazione formale della validità dell'algoritmo.
Cercando su wikipedia, la dimostrazione non mi è molto chiara...
https://it.wikipedia.org/wiki/Algoritmo_di_Euclide

C'è qualcuno capace di aiutarmi?

[axpgn]

Dati i due interi positivi $a>b$, sappiamo che esistono due interi $q$ ed $r$ tali che $a=bq+r$ con $0<=r Ora, se un intero divide sia $a$ che $b$ allora necessariamente divide anche $r$ perciò possiamo ripetere il giochetto fino a trovare un resto a zero, a quel punto l'ultimo resto è il MCD dei due numeri iniziali ...

Spiegazione poco formale ma spero utile ...

Cordialmente, Alex

[dr00ster]

Semplice, chiaro e conciso! Grazie mille!