Division mit Rest/Z/Fakt/Beweis

Beweis

Zur Existenz. Bei ${}n=0$ ist ${}q=r=0$ eine Lösung. Es sei ${}n$ positiv. Da ${}d$ positiv ist, gibt es ein Vielfaches ${}ad\geq n$. Daher gibt es auch eine Zahl ${}q$ mit $qd\leq n$ und $(q+1)d>n$. Es sei ${}r:=n-qd$. Dann ist

${}qd\leq qd+r<qd+d\,$

und daher ist ${}0\leq r<d$ wie gewünscht. Bei ${}n$ negativ kann man schreiben ${}-n={\tilde {q}}d+{\tilde {r}}$ nach dem Resultat für positive Zahlen. Daraus ergibt sich

$n=(-{\tilde {q}})d-{\tilde {r}}={\begin{cases}(-{\tilde {q}})d+0{\text{ bei }}{\tilde {r}}=0\\(-{\tilde {q}}-1)d+d-{\tilde {r}}{\text{ sonst}}\,.\end{cases}}$

Im zweiten Fall erfüllen ${}q=-{\tilde {q}}-1$ und ${}r=d-{\tilde {r}}$ die Bedingungen.
Zur Eindeutigkeit. Es sei ${}qd+r=n={\tilde {q}}d+{\tilde {r}}$, wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung ${}{\tilde {r}}\geq r$. Dann gilt ${}(q-{\tilde {q}})d={\tilde {r}}-r$. Diese Differenz ist nichtnegativ und kleiner als ${}d$, links steht aber ein Vielfaches von ${}d$, sodass die Differenz ${}0$ sein muss und die beiden Darstellungen überein stimmen.

Zur bewiesenen Aussage