Division mit Rest/N/Induktion/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Zur Existenz.  Dies wird durch Induktion über bewiesen. Es sei fixiert. Der Induktionsanfang ergibt sich direkt mit und . Für den Induktionsschluss sei die Aussage für bewiesen, d.h. wir haben eine Darstellung mit und müssen eine ebensolche Darstellung für finden. Wenn ist, so ist

und wegen ist dies eine gesuchte Darstellung. Ist hingegen , so ist

und dies ist eine gesuchte Darstellung.
Zur Eindeutigkeit. Sei , wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung . Dann gilt . Diese Differenz ist nichtnegativ und kleiner als , links steht aber ein Vielfaches von , so dass die Differenz sein muss und die beiden Darstellungen übereinstimmen.

Zur bewiesenen Aussage