Wir betrachten zum Nachweis der Existenz die erststufige Aussage

${\displaystyle \forall d{\left(d\geq 1\rightarrow \exists q\exists r{\left(m=dq+r\wedge r\leq d\wedge \neg r=d\right)}\right)},}$

die ${\displaystyle {}m}$ als einzige freie Variable besitzt. Für ${\displaystyle {}m=0}$ ist die Aussage mit ${\displaystyle {}q=0}$ und

${\displaystyle {}r=0\,}$

richtig. Zum Beweis des Induktionsschritts sei

${\displaystyle {}m=dq+r\,}$

mit den angegebenen Eigenschaften. Daher ist

${\displaystyle {}m+1=dq+r+1\,.}$

Wenn ${\displaystyle {}r'=r+1}$ kleiner als ${\displaystyle {}d}$ ist, so erfüllen ${\displaystyle {}q,r'}$ die geforderten Eigenschaften. Bei ${\displaystyle {}r+1\geq d}$ muss ${\displaystyle {}r+1=d}$ gelten. Dann ist

${\displaystyle {}m+1=dq+r+1=dq+d=d(q+1)\,,}$

so dass ${\displaystyle {}q+1,0}$ das Geforderte leisten. Für die Eindeutigkeit siehe Aufgabe.