Algorytm dzielenia z reszta w Z

[GothicIIIbez]

Założenia:
* \(\displaystyle{ a,b Z,b 0}\)
* b nie dzieli a
Teza:
* istnieją dokładnie dwie pary liczb \(\displaystyle{ (q,r) \mathbb{Z} \mathbb{Z}}\):
(1) \(\displaystyle{ a=qb+r}\)
(2) \(\displaystyle{ |r|}\)

[limes123]

(i)a>b wtedy bedzie q raz z minusem raz z plusem i podobnie r (skoro b nie dzieli a to beda 2 i nie moze byc wiecej, bo |r| sprobuj sam bo pewnie podobnie pojdzie