===== File: euclide.txt =====

============================================================================
Il metodo di Euclide per calcolare il massimo comun divisore
============================================================================

Il metodo si basa sulla seguente osservazione:

Siano m e n due interi positvi:
  - se m = n allora mcd(m, n) = m = n
  - se m > n allora mcd(m, n) = mcd(m-n, n)
  - se m < n allora mcd(m, n) = mcd(m, n-m)

DIMOSTRAZIONE:

E` sufficiente considerare il caso m>n, e mostrare che
i divisori comuni di m e n coincidono con i divisori comuni di m-n e n.

1) Sia k divisore comune di m e n.
   Allora si ha che: m = k * u (per qualche u>0)
                     n = k * v (per qualche v>0)
   Quindi m - n = k * (u-v).
   Da m>n segue u>v, e quindi k e` un divisore di m-n.

2) Sia k divisore comune di m-n e n.
   Allora si ha che: m-n = k * x (per qualche x>0)
                     n   = k * y (per qualche y>0)
   Quindi m = m-n+n = k * (x+y), e quindi k divide m.