Aufgabensammlung Mathematik: Teilbarkeit durch 23

Teilbarkeit durch 23

Beweise, dass $5^{2u}-2^{u}$ für $u\in \mathbb {N} _{0}$ durch 23 teilbar ist.

Verfahren mit direktem Vergleich

Lösungsweg 1

Frage: Über welche Variable kann die Induktion geführt werden?

$u$

Frage: Wie lautet der Induktionsanfang? Welches ist die kleinste mögliche Zahl, für die die Teilbarkeit gilt?

Der Induktionsanfang ist für $u=0$ zu führen. Die Formel ergibt dann:

$5^{2\cdot 0}-2^{0}=5^{0}-2^{0}=1-1=0$

0 ist durch 23 teilbar (generell ist jede natürliche Zahl Teiler von 0).

Hinweis: Der Induktionsanfang könnte theoretische auch für $u=1$ geführt werden. Dann hätte man aber die Aussage „$5^{2u}-2^{u}$ ist durch 23 teilbar“ nur für natürliche $u\geq 1$ bewiesen. Jedoch gilt die Aussage „$5^{2u}-2^{u}$ ist durch 23 teilbar“ auch für $u=0$. Damit auch dieser Fall vom Beweis abgedeckt wird, wählt man als Induktionsanfang $u=0$.

Frage: Wie lautet die Induktionsvoraussetzung, und wie lautet die Induktionsbehauptung?

Induktionsvoraussetzung: $5^{2u}-2^{u}$ durch 23 teilbar.

Induktionsbehauptung: $5^{2\cdot (u+1)}-2^{u+1}$ ist 23 teilbar.

Frage: Über welchen Weg kannst du die Induktionsbehauptung mit Hilfe der Induktionsvoraussetzung beweisen?

Der Term $5^{2\cdot (u+1)}-2^{u+1}$ 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 $5^{2u}-2^{u}$ 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.

Aufgabe: Finde Termumformungen, um die Induktionsbehauptung mit Hilfe der Induktionsvoraussetzung zu beweisen.

Die Termumformungen lauten:

${\begin{aligned}5^{2\cdot (u+1)}-2^{u+1}&=5^{2u+2}-2^{u+1}\\&=5^{2u}\cdot 5^{2}-2^{u}\cdot 2\\&=5^{2u}\cdot 5^{2}-5^{2}\cdot 2^{u}+5^{2}\cdot 2^{u}-2^{u}\cdot 2\\&=5^{2}\cdot (5^{2u}-2^{u})+2^{u}\cdot (5^{2}-2)\\&=(5^{2u}-2^{u})\cdot 5^{2}+2^{u}\cdot 23\\\end{aligned}}$

Der Term $5^{2u}-2^{u}$ in der ersten Klammer ist nach Induktionsvoraussetzung durch 23 teilbar. Somit ist auch der erste Summand $(5^{2u}-2^{u})\cdot 5^{2}$ 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 $2^{u}\cdot 23$ ist durch 23 teilbar. Damit ist die gesamte Summe durch 23 teilbar, weil beide Summanden dieser Summe durch 23 teilbar sind.

Beweis 1

Aussageform, deren Allgemeingültigkeit in $\mathbb {N} _{0}$ bewiesen werden soll:

$A(u):5^{2u}-2^{u}{\text{ ist durch 23 teilbar}}$

1. Induktionsanfang:

$A(0)$ ist erfüllt:

$5^{2\cdot 0}-2^{0}=5^{0}-2^{0}=1-1=0$

$0$ ist durch 23 teilbar.

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

$5^{2u}-2^{u}$ ist durch 23 teilbar.

2b. Induktionsbehauptung:

$5^{2\cdot (u+1)}-2^{u+1}$ ist durch 23 teilbar.

2c. Beweis des Induktionsschritts:

${\begin{aligned}5^{2\cdot (u+1)}-2^{u+1}&=5^{2u+2}-2^{u+1}\\&=5^{2u}\cdot 5^{2}-2^{u}\cdot 2\\&=5^{2u}\cdot 5^{2}-5^{2}\cdot 2^{u}+5^{2}\cdot 2^{u}-2^{u}\cdot 2\\&=5^{2}\cdot (5^{2u}-2^{u})+2^{u}\cdot (5^{2}-2)\\&=\underbrace {\underbrace {(5^{2u}-2^{u})} _{\text{teilbar durch 23 wegen Induktionsvoraussetzung}}\cdot 5^{2}+\underbrace {2^{u}\cdot 23} _{\text{teilbar durch 23}}} _{\text{teilbar durch 23}}\\\end{aligned}}$

Verfahren mit Kongruenzen

Die Aufgabe kann mit Hilfe von Kongruenzen so formuliert werden:

Beweise: Für alle $u\in \mathbb {N} _{0}$ ist $5^{2u}-2^{u}\equiv 0\mod 23$.

Lösungsweg 2

Frage: Über welche Variable kann die Induktion geführt werden?

$u$

Frage: Wie lautet der Induktionsanfang? Welches ist die kleinste mögliche Zahl, für die die Teilbarkeit gilt?

Der Induktionsanfang ist für $u=0$ zu führen. Die Formel ergibt dann:

$5^{2\cdot 0}-2^{0}=5^{0}-2^{0}=1-1=0\equiv 0\mod 23$

Also ist die behauptete Kongruenz für $u=0$ gegeben.

Frage: Wie lautet die Induktionsvoraussetzung, und wie lautet die Induktionsbehauptung?

Induktionsvoraussetzung: $5^{2u}-2^{u}\equiv 0\mod 23$

Induktionsbehauptung: $5^{2(u+1)}-2^{u+1}\equiv 0\mod 23$

Aufgabe: Finde Termumformungen, um die Induktionsbehauptung mit Hilfe der Induktionsvoraussetzung zu beweisen.

Die Termumformungen lauten:

${\begin{aligned}{\begin{array}{lrll}&5^{2(u+1)}-2^{u+1}&\equiv 0\mod 23\\\Leftrightarrow &5^{2u}\cdot 5^{2}-2^{u}\cdot 2&\equiv 0\mod 23\\\Leftrightarrow &5^{2u}\cdot 5^{2}-5^{2}\cdot 2^{u}+5^{2}\cdot 2^{u}-2^{u}\cdot 2&\equiv 0\mod 23\\\Leftrightarrow &5^{2}\cdot {\color {Blue}\left(5^{2u}-2^{u}\right)}+2^{u}\cdot \left(5^{2}-2\right)&\equiv 0\mod 23&\left|\ {\color {Blue}{\text{Induktionsvoraussetzung: }}5^{2u}-2^{u}\equiv 0\mod 23}\right.\\\Leftrightarrow &5^{2}\cdot {\color {Blue}0}+2^{u}\cdot \left(5^{2}-2\right)&\equiv 0\mod 23\\\Leftrightarrow &2^{u}\cdot \left(5^{2}-2\right)&\equiv 0\mod 23&\left|\ 5^{2}-2=23\equiv 0\mod 23\right.\\\Leftrightarrow &2^{u}\cdot 0&\equiv 0\mod 23\\\Leftrightarrow &0&\equiv 0\mod 23\\\end{array}}\end{aligned}}$

Beweis 2

Aussageform, deren Allgemeingültigkeit in $\mathbb {N} _{0}$ bewiesen werden soll:

$A(u):5^{2u}-2^{u}\equiv 0\mod 23$

1. Induktionsanfang:

$A(0)$ ist erfüllt:

$5^{2\cdot 0}-2^{0}=5^{0}-2^{0}=1-1=0\equiv 0\mod 23$

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

$5^{2u}-2^{u}\equiv 0\mod 23$

2b. Induktionsbehauptung:

$5^{2(u+1)}-2^{u+1}\equiv 0\mod 23$

2c. Beweis des Induktionsschritts:

${\begin{aligned}{\begin{array}{lrll}&5^{2(u+1)}-2^{u+1}&\equiv 0\mod 23\\\Leftrightarrow &5^{2u}\cdot 5^{2}-2^{u}\cdot 2&\equiv 0\mod 23\\\Leftrightarrow &5^{2u}\cdot 5^{2}-5^{2}\cdot 2^{u}+5^{2}\cdot 2^{u}-2^{u}\cdot 2&\equiv 0\mod 23\\\Leftrightarrow &5^{2}\cdot {\color {Blue}\left(5^{2u}-2^{u}\right)}+2^{u}\cdot \left(5^{2}-2\right)&\equiv 0\mod 23&\left|\ {\color {Blue}{\text{Induktionsvoraussetzung: }}5^{2u}-2^{u}\equiv 0\mod 23}\right.\\\Leftrightarrow &5^{2}\cdot {\color {Blue}0}+2^{u}\cdot \left(5^{2}-2\right)&\equiv 0\mod 23\\\Leftrightarrow &2^{u}\cdot \left(5^{2}-2\right)&\equiv 0\mod 23&\left|\ 5^{2}-2=23\equiv 0\mod 23\right.\\\Leftrightarrow &2^{u}\cdot 0&\equiv 0\mod 23\\\Leftrightarrow &0&\equiv 0\mod 23\\\end{array}}\end{aligned}}$

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 $5^{2}\cdot 2^{u}$ 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 $u+1$ benutzt.
• Um die Induktionsvoraussetzung zu benutzen, benötigen wir einen gleichartigen Term mit $u$.
• Wir müssen also $5^{2\cdot (u+1)}-2^{u+1}$ so umformen, dass irgendwo $5^{2u}-2^{u}$ steht.
• Die ersten beiden Umformungen ergeben sich sozusagen automatisch, damit im Exponenten $u$ statt $u+1$ steht.
• Die Induktionsvoraussetzung besagt, dass von $5^{2u}$ jeweils $2^{u}$ abzuziehen ist. Also fügen wir diese Subtraktion ein unter Berücksichtigung des Faktors $5^{2}$. 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.

Brute Force

Man berechnet tabellarisch die Module für $5^{2u}$ und $2^{u}$.

u	$5^{2u}$	$2^{u}$	Differenz
0	1	1	0
1	2	2	0
2	4	4	0
3	8	8	0
4	16	16	0
5	9	9	0
6	18	18	0
7	13	13	0
8	3	3	0
9	6	6	0
10	12	12	0
11	1	1	0

Ab $u=11$ wiederholen sich die Werte zyklisch.

Modulare Arithmetik

Die Operationen $5^{2u}=25^{u}=(25-23)^{u}=2^{u}$ und $2^{u}$ stellen im Ring $\mathbb {Z} _{23}$ die gleiche Operation $2^{u}$ dar.