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\ge n$.  Daher gibt es auch eine Zahl $q$ mit $qd\le n$ und $(q+1)d>n$. Es sei  $r:=n-qd$.  Dann ist

$qd\le qd+r<qd+d$

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

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

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}\ge 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 übereinstimmen.

Zur bewiesenen Aussage