1) Tomamos
,
.
2) Hacemos la división entera entre
y
de manera que obtenemos:
donde
es el cociente y
es el resto.
3) Si
, continuamos.Hacemos la división entera entre
y
de manera que obtenemos:
donde
es el cociente y
es el resto.
4) Repetimos el proceso:
donde
es el cociente y
es el resto.
Hasta llegar a un resto
.
5) Entonces
.
6) Para obtener
verificando la condición (1), despejamos en cada ecuación el resto:
y lo vamos sustiyendo en la ecuación anterior empezando por el final:
y así sucesivamente. Al final tendremos
como combinación lineal entera de
y
(de
y
).
