Aufgabensammlung Mathematik: Teilbarkeit durch 23
Teilbarkeit durch 23
Beweise, dass für durch 23 teilbar ist.
Verfahren mit direktem Vergleich
Lösungsweg 1
Der Induktionsanfang ist für zu führen. Die Formel ergibt dann:
0 ist durch 23 teilbar (generell ist jede natürliche Zahl Teiler von 0).
Hinweis: Der Induktionsanfang könnte theoretische auch für geführt werden. Dann hätte man aber die Aussage „ ist durch 23 teilbar“ nur für natürliche bewiesen. Jedoch gilt die Aussage „ ist durch 23 teilbar“ auch für . Damit auch dieser Fall vom Beweis abgedeckt wird, wählt man als Induktionsanfang .
Induktionsvoraussetzung: durch 23 teilbar.
Induktionsbehauptung: ist 23 teilbar.
Der Term der Induktionsbehauptung wird so lange umgeformt, bis wir einen Term erhalten, bei der wir die Teilbarkeit einzelner Teilterme durch 23 beweisen können (So wissen wir aus der Induktionsvoraussetzung, dass ein Teilterm der Form durch 23 teilbar ist). Durch Sätze wie „Die Summe zweier durch 23 teilbarer Terme ist wieder durch 23 teilbar“, können wir dann aus der Teilbarkeit der Teilterme durch 23 auf die Teilbarkeit des gesamten Terms durch 23 schließen.
Die Termumformungen lauten:
Der Term in der ersten Klammer ist nach Induktionsvoraussetzung durch 23 teilbar. Somit ist auch der erste Summand durch 23 teilbar (das Produkt einer durch 23 teilbaren Zahl mit einer beliebigen anderen natürlichen Zahl ist wieder durch 23 teilbar). Auch der zweite Summand ist durch 23 teilbar. Damit ist die gesamte Summe durch 23 teilbar, weil beide Summanden dieser Summe durch 23 teilbar sind.
Beweis 1
ist erfüllt:
ist durch 23 teilbar.
- ist durch 23 teilbar.
- ist durch 23 teilbar.
Verfahren mit Kongruenzen
Die Aufgabe kann mit Hilfe von Kongruenzen so formuliert werden:
Beweise: Für alle ist .
Lösungsweg 2
Der Induktionsanfang ist für zu führen. Die Formel ergibt dann:
Also ist die behauptete Kongruenz für gegeben.
Induktionsvoraussetzung:
Induktionsbehauptung:
Die Termumformungen lauten:
Beweis 2
ist erfüllt:
Woher kommt die Idee der geschickten Termumformung?
Auch dieser Beweis ist nicht „vom Himmel gefallen“, sondern entspringt systematischem Nachdenken. Der „Trick“ bei den Termumformungen liegt darin, dass von Zeile 2 zu Zeile 3 eine Null eingeschoben wird, nämlich der Term nacheinander subtrahiert und addiert wird. Dass es gerade dieser Term sein musste, ergibt sich aus folgenden Gedanken:
- Am Anfang haben wir einen Term, der zur Induktionsbehauptung gehört, also benutzt.
- Um die Induktionsvoraussetzung zu benutzen, benötigen wir einen gleichartigen Term mit .
- Wir müssen also so umformen, dass irgendwo steht.
- Die ersten beiden Umformungen ergeben sich sozusagen automatisch, damit im Exponenten statt steht.
- Die Induktionsvoraussetzung besagt, dass von jeweils abzuziehen ist. Also fügen wir diese Subtraktion ein unter Berücksichtigung des Faktors . Damit die Gleichheit erhalten bleibt, muss dieser Term gleichzeitig addiert werden.
Damit kann für den ersten Teil die Induktionsvoraussetzung angewendet werden. Für den Rest des Terms in Zeile 3 ergibt sich die eigentliche Behauptung durch einfache Rechnung.
Allgemeine Hinweise, wie man einen solchen Schritt findet, stehen bei Beispielen zur vollständigen Induktion.