Aus dem Tutorium.
Man zeige mithilfe einer endlichen geometrischen Reihe, dass für alle $k,\ n\in\N_{\geqslant1}$ gilt:
\[
k \mid n \implies 2^k-1 \mid 2^n-1\quad.
\]
Nun: Seien $k,\ n\in\N_{\geqslant1}$. Es gelte $k\mid n$, d.h es gebe ein $q\in\N$ mit $n=q\cdot k$.
Der Fall $q=0$ tritt nicht ein. Der Fall $q=1$ ist trivial. (Ja, wirklich! Aus $k=n$ folgt $2^k-1=2^n-1$, also auch $2^k-1 \mid 2^n-1$.)
Im Fall $q>1$ folgt
\[
\begin{array}{rcl}
2^n-1 &=& \displaystyle\sum_{i=0}^{n-1} 2^i\\
&=& \displaystyle\sum_{i=0}^{k-1} 2^i+\displaystyle\sum_{i=k}^{n-1} 2^i\\
&=& 2^k-1+\displaystyle\sum_{i=k}^{n-1} 2^i\\
&=& 2^k-1+2^k\cdot\displaystyle\sum_{i=0}^{n-1-k} 2^i\quad.\\
\end{array}
\]
Auf die letzte Summe können wir diese Umformungen natürlich erneut anwenden (sofern $q>2$) und erhalten
\[
\begin{array}{rcl}
2^n-1 &=& \displaystyle\sum_{i=0}^{n-1} 2^i\\
&=& 2^k-1+\displaystyle\sum_{i=k}^{n-1} 2^i\\
&=& 2^k-1+2^k\cdot\displaystyle\sum_{i=0}^{n-1-k} 2^i\\
&=& 2^k-1+2^k\cdot\left(2^k-1+2^k\cdot\displaystyle\sum_{i=0}^{n-1-2\cdot k} 2^i\right)\quad.
\end{array}
\]
Wir sehen, dass wir auf diese Weise genau $k$ Mal den Faktor $2^k$ ausklammern können und am Ende einen Ausdruck der Form
\[
2^n-1 = 2^k-1+2^k\cdot\left(2^k-1+2^k\cdot\left(\ldots\cdot\left(\sum_{i=0}^{n-1-q\cdot k} 2^i\right)\ldots\right)\right)
\]
erhalten.
Dabei ist die Summe $\sum_{i=0}^{n-1-q\cdot k} 2^i$ gleich Null, denn die obere Summationsgrenze ist $-1$ und damit kleiner als die untere. Also ist diese Summe durch $2^k-1$ teilbar. Multiplikation mit $2^k$ ändert daran nichts, ebensowenig wie die anschließende Addition von $2^k-1$. Indem wir uns auf diese Weise durch die Klammerebenen arbeiten, sehen wir, dass die gesamte rechte Seite durch $2^k-1$ teilbar ist, also auch die linke, und dies war zu zeigen.
Kann man in diesem Beweis auf die Pünktchenschreibweise verzichten?
Ja, man kann! Und zwar mit Abschnittsinduktion. Dazu mehr in einem späteren Post.
