Algoritmo de Euclides

Después de definir MCD, ver más teoremas de divisibilidad y definir a los primos. Tenemos lo necesario para desarrollar el Algoritmo de Euclides.

Lema.

Sean , . Para todo

Proof.

Sean con . Sea .


Veamos que .

Sea , como ent. y .
Como y , ent. .
Así, y , ent. .

Sea , es decir tal que y .
Como , ent. .
Así, y , ent.
Por lo tanto y , ent.
Finalmente, como tenemos

Ejemplo.

.

Teorema. (Algortimo de Euclides)

Sean ,
Si , ent. .
Si aplicando el algoritmo de la división tenemos

Tenemos que , el útlimo residuo no nulo de ese proceso, es .
Más aún, despejando los residuos obtengo una combinación lineal entera que me da .

Ejemplo.

Proof.