Division mit Rest/N/Induktion/Fakt/Beweis

Beweis

Zur Existenz.  Dies wird durch Induktion über $n$ bewiesen. Es sei  $d>0$  fixiert. Der Induktionsanfang für  $n=0$  ergibt sich direkt mit  $q=0$  und  $r=0$.  Für den Induktionsschluss sei die Aussage für $n$ bewiesen, d.h. wir haben eine Darstellung  $n=dq+r$  mit  $r<d$  und müssen eine ebensolche Darstellung für $n+1$ finden. Wenn  $r<d-1$  ist, so ist

$n+1=dq+r+1$

und wegen  $r+1<d$  ist dies eine gesuchte Darstellung. Ist hingegen  $r=d-1$,  so ist

$n+1=dq+r+1=dq+d=d(q+1)+0,$

und dies ist eine gesuchte Darstellung.
Zur Eindeutigkeit. 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