Algoritmo de la División

Teorema. (Algoritmo de la División)

Sean , , entonces, existen tales que

llamados cociente y residuo, y dichos enteros son únicos.

Proof.

Sean .
Caso 1.
Considero los múltiplos de , ie. los de la forma con . Me fijo en su diferencia con , ie. y considero

Es claro que , ¿tiene este conjunto un mínimo elemento?
Para aplicar PBO, necesitamos ver que :
Si , y ent. .
Si , , ent .
Ahora, por el PBO tiene un elemento mínimo, digamos . Sabiemos que , es decir

Así, con
PD.
Sup PRAA que , ent.

Ent. . Pero como , ent

! sería un elemento de menor que el número de !

Caso 2.
Tenemos , dividiendo entre por el caso 1, existen tales que

ent,

Unicidad:
Supongamos que son tales que

con y .
PD. y
Tenemos

Si , tendríamos

Pero , y se tiene que !
Ent, es decir y y ent
, por tanto .