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}}\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 bewiesenen Aussage