Division mit Rest/N/Induktion/Fakt/Beweis/Aufgabe/Lösung

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

Zur gelösten Aufgabe