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

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

Il metodo si basa sulla seguente osservazione:

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

DIMOSTRAZIONE:

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

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

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