Dimostrazione MCD

[Sk_Anonymous]

Ciao a tutti. Chi mi aiuta a dimostrare questo:
Siano $a$,$b$,$d=MCD(a,b)$ e $r=a mod b$. Allora $d=MCD(b,r)$.

[Sk_Anonymous]

Ragionamento un tantino sottile...
Possiamo supporre $a>=b$ altrimenti si scambia a con b. Eseguita la divisione tra a e b si ha :
(1) $a=bq+r$
da cui
(2) $r=a-bq$
Osserviamo ora che $MCD(a,b) $, dividendo sia a che b, per la (2) divide anche r (oltre che b) e quindi divide
pure $MCD(b,r)$
Dunque :
(1) $MCD(a,b)<=MCD(b,r) $
Analogamente dalla (1) si ricava che $MCD(b,r)$, dividendo sia b che r, divide pure a. E dividendo sia a che b, divide
anche $MCD(a,b)$. Pertanto :
(2) $MCD(b,r)<=MCD(a,b)$
Da (1) e da (2) segue che $MCD(a,b)=MCD(b,r) $ che è la tesi.

[Sk_Anonymous]

Io ho provato, ma mi sono bloccato. Allora:
$d=MCD(a,b)=>{ ( a/d=q_(ad) ),( b/d=q_(bd) ):} <=> { ( a=d*q_(ad) ), ( b=d*q_(bd) ) :}$
Ora: $a=q_(ab)*b+r <=> d*q_(ad)=q_(ab)*d*q_(bd)+r <=> r=d*q_(ad)-q_(ab)*d*q_(bd) <=> r=d(q_(ad)-q_(ab)*q_(bd))$
Quindi $d$ è divisore anche di $r$. Ora come faccio a verificare che $MCD(b,r)=d$?

[Sk_Anonymous]

Grazie mille ciromario!!