Natürliche Zahlen/Division mit Rest/Einführung/Textabschnitt

Jede natürliche Zahl lässt sich bekanntlich als eine Ziffernfolge „im Zehnersystem“ ausdrücken. Dies beruht auf der (sukzessiven) Division mit Rest. Eine positive natürliche Zahl ist nicht durch jede natürliche Zahl teilbar, die Division mit Rest liefert eine Operation, die stets durchführbar ist.

Satz

Es sei ${}d$ eine fixierte positive natürliche Zahl.

Dann gibt es zu jeder natürlichen Zahl ${}n$ eine eindeutig bestimmte natürliche Zahl ${}q$ und eine eindeutig bestimmte natürliche Zahl ${}r$ , ${}0\leq r\leq d-1$ , mit

${}n=qd+r\,.$

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$ , so dass die Differenz ${}0$ sein muss und die beiden Darstellungen übereinstimmen.

\Box

Bei der Division mit Rest nennt man auch ${}n$ Dividend und ${}d$ Divisor. Die Zahl ${}q$ nennt man Quotienten oder ganzzahligen Anteil und ${}r$ den Rest.

Bemerkung

Zu gegebenen natürlichen Zahlen ${}n,d$ mit ${}d\geq 1$ findet man die Division mit Rest, also die Darstellung ${}n=qd+r$ , indem man der Reihe nach die Vielfachen von ${}d$ betrachtet. Das größte Vielfache von ${}d$ (gleich oder) unterhalb von ${}n$ ist das gesuchte ${}qd$ , insbesondere muss das nächste Vielfache ${}(q+1)d>n$ sein. Der Rest ergibt sich dann als ${}r=n-qd$ .