El algoritmo de Euclides para calcular
el máximo común divisor D de a y b.
a = c
1
b+r
1
b = c
2
r
1
+r
2
r
1
=c
3
r
2
+r
3
r
2
=c
4
r
3
+
0
r
3
=D
D=xa+yb
Si D=1, entonces 1=xa+yb