Beweis
Wir betrachten zum Nachweis der Existenz die erststufige Aussage
-
die
als einzige freie Variable besitzt. Für
ist die Aussage mit
und
-
![{\displaystyle {}r=0\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f0dc4f7163ab8a38a07043bb24d089bc1fae28b)
richtig. Zum Beweis des Induktionsschritts sei
-
![{\displaystyle {}m=dq+r\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/540f1c321de9b566dd89c3114a29c069633ee4d0)
mit den angegebenen Eigenschaften. Daher ist
-
![{\displaystyle {}m+1=dq+r+1\,.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7afed4202db52c9de84355746a94149fc0bce9d)
Wenn
kleiner als
ist, so erfüllen
die geforderten Eigenschaften. Bei
muss
nach
Aufgabe
gelten.
Dann ist
-
![{\displaystyle {}m+1=dq+r+1=dq+d=d(q+1)\,,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5eb6e3d2f94238916f44bc386da11fdcca6b7f8e)
so dass
und
das Geforderte leisten. Für die Eindeutigkeit siehe
Aufgabe.