Aufgabensammlung Mathematik: Teilbarkeit durch 2^(k+2)

Teilbarkeit durch $2^{k+2}$

1. Beweise, dass $3^{(2^{k})}-1$ für $k\in \mathbb {N} _{\geq 1}$ durch $2^{k+2}$ teilbar ist.

2. Als zusätzliche Herausforderung kannst du versuchen, die folgende, allgemeinere Aussage zu beweisen:

$u^{(2^{k})}-1$ ist für ungerade $u\in \mathbb {N}$ und $k\in \mathbb {N} _{\geq 1}$ durch $2^{k+2}$ teilbar.

Beweis zu 1.

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

$3^{2^{k}}-1=2^{k+2}\cdot p\ ,p\in \mathbb {N} _{\geq 1}$

1. Induktionsanfang:

$3^{2^{1}}-1=8=2^{1+2}\cdot 1.$

2. Induktionsschritt

2a. Induktionsvoraussetzung:

$3^{2^{k}}-1=2^{k+2}\cdot p\ ,p\in \mathbb {N} _{\geq 1}$ bzw. $3^{2^{k}}=2^{k+2}\cdot p+1.$

2b. Induktionsbehauptung:

$3^{2^{k+1}}-1=2^{k+3}\cdot q\ ,q\in \mathbb {N} _{\geq 1}.$

2c. Beweis des Induktionsschluss:

${\begin{aligned}3^{2^{k+1}}-1=\left(3^{2^{k}}\right)^{2}-1&{\overset {IV}{=}}\left(2^{k+2}\cdot p+1\right)^{2}-1\\&=2^{2k+4}\cdot p^{2}+2^{k+3}\cdot p\\&=2^{k+3}\underbrace {\left(2^{k+1}\cdot p^{2}+p\right)} _{=:q}.\\\end{aligned}}$

Beweis zu 2.

Lösungshinweis:

Ingredienzien des Beweises sind

1) die wohlvertraute Formel $\left(a+b\right)\left(a-b\right)=a^{2}-b^{2}$

2) $\alpha \mid a\ und\ \beta \mid b\Rightarrow \alpha \cdot \beta \mid a\cdot b$

3) $k\ ungerade\Rightarrow k^{n}\ ungerade,\ k,n\in \mathbb {N} _{\geq 1}$.

Lösung:

1. Induktionsanfang:

Für $k=1$ ist die Aussage korrekt. Mit 1) ist $u^{2^{1}}-1=\left(u+1\right)\left(u-1\right)$. Da u ungerade ist, müssen die Ausdrücke in den beiden Klammern jeweils gerade sein. D.h. eine der Zahlen $u+1$ und $u-1$ ist durch 4 teilbar und die andere durch 2. Wegen 2) folgt, dass dann $u^{2^{1}}-1=\left(u+1\right)\left(u-1\right)$ durch 8 teilbar ist.

2. Induktionsschritt

2a. Induktionsvoraussetzung:

$u^{2^{k}}-1$ ist durch $2^{k+2}$ teilbar.

2b. Induktionsbehauptung:

$u^{2^{k+1}}-1$ ist durch $2^{k+3}$ teilbar.

2c. Beweis des Induktionsschluss:

Mit 1) gilt $u^{2^{k+1}}-1=u^{2^{k}\cdot 2}-1=\left(u^{2^{k}}\right)^{2}-1=\left(u^{2^{k}}+1\right)\left(u^{2^{k}}-1\right)$. Der Term in der ersten Klammer ist gerade, d.h. durch 2 teilbar. Dies folgt letztlich aus 3). Der Term in der zweiten Klammer ist laut IV durch $2^{k+2}$ teilbar. Demnach muss wegen 2) das Produkt der Klammern durch $2\cdot 2^{k+2}=2^{k+3}$ teilbar sein.