Guide

Algoritmo di Euclide per il calcolo del Massimo Comune Divisore (MCD) di due interi (tempo di lavoro O((lg n)2) operazioni su bit):
INPUT: due interi non negativi a e b (a minore uguale di b)

OUTPUT: MCD di a e b

1) mentre ripeti:

poni r = a mod b; a = b; b = r; (ricordiamo che a mod b restituisce il resto della divisione intera tra a e b)

2) restituisci a

Algoritmo di Euclide esteso:

INPUT: due interi non negativi a e b,

OUTPUT: d = MCD (a,b) e gli interi x, y tali che ax + by = d.

1) Se b=0 allora poni d=a, x=1, y=0 e restituisci (d, x, y)

2) Poni x2=1, x1=0, y1=1.

3) Mentre b>0 fai i seguenti

3.1) q=divisione intera di a/b , r= a - qb, x= x2 - qx1 , y= y2 - qy1 .

3.2) a =b, b =r, x2 =x1 , x1 =x, y2 =y1 , y1 =y.

4) Poni d= a, x= x2 , y= y2 , e restituisci (d,x,y).