Teilbarkeit durch $7$

Aus dem Tutorium.

Sei $z$ eine im Dezimalsystem mehrstellige ganze Zahl. Man bilde aus $z$ die Zahl ${z'\in\Z}$, indem man die Einerstelle von $z$ streiche und von der verbleibenden Zahl das Doppelte der gestrichenen Ziffer subtrahiere.
Man zeige: Genau dann ist $z'$ durch $7$ teilbar, wenn $z$ durch $7$ teilbar ist. Man entwickle daraus einen Algorithmus, mit dem man die Teilbarkeit einer ganzen Zahl ${n\neq0}$ durch $7$ in ${\mathcal O(\log(\abs n))}$ Schritten prüfen kann.

Und das geht so:

Sei ${n\in\N_{\geqslant1}}$. Seien ${a_0,\ldots,a_n\in\{0,\ldots,9\}}$, und es gelte ${a_1\neq0}$.
Setze ${z:=\displaystyle\sum_{k=0}^{n}a_k\,10^k}$ und ${z':=-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k}$.

Wir müssen zeigen, dass aus ${7\divides z'}$ die Aussage ${7\divides z}$ folgt und umgekehrt.

Gelte also ${7\divides z'}$. Dann gibt es ${l\in\Z}$ mit ${7\,l=z'}$, d.h. ${7\,l=-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k}$. Es sind die folgenden Aussagen äquivalent: \[ \begin{array}{rcl} 7\,l&=&-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k\\ 70\,l&=&10\cdot\left(-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k\right)\\ 70\,l&=&-20\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^{k+1}\\ 70\,l&=&-20\,a_0+\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k}\\ 70\,l+20\,a_0&=&\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k}\\ 70\,l+21\,a_0&=&a_0+\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k}\\ 70\,l+21\,a_0&=&\displaystyle\sum_{k=0}^{n}a_{k}\,10^{k}\\ 70\,l+21\,a_0&=&z\\ \end{array} \]
Es gilt also ${70\,l+21\,a_0=z}$, und wegen ${7\divides70\,l}$ und ${7\divides21\,a_0}$ folgt ${7\divides70\,l+21\,a_0}$, d.h. ${7\divides z}$. Dies war eine der zu zeigenden Behauptungen.

Die andere Richtung der Äquivalenzaussage erhält man, indem man annimmt, $z$ sei durch ${7}$ teilbar, beachtet, dass mit $z$ auch $z-21\,a_0$ durch $7$ teilbar ist und die oben stehende Äquivalenzenkette von unten nach oben liest. Genauer: \[ \begin{array}{rcl} 7\divides z &\implies& 7\divides z-21\,a_0\\ &\implies& 7\divides -20\,a_0+\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k}\\ &\implies& 7\divides 10\cdot\left(-2\,a_0+\displaystyle\sum_{k=1}^{n}a_{k}\,10^{k-1}\right)\\ &\implies& 7\divides 10\cdot\left(-2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k\right)\\ &\implies& 7\divides -2\,a_0+\displaystyle\sum_{k=0}^{n-1}a_{k+1}\,10^k\\ &\implies& 7\divides z'\\ \end{array} \]
Wie der Algorithmus aussieht, ist damit klar: Ist die gegebene Zahl ${n\in\Z}$ negativ, so gehe man zu ihrem Betrag über. Ist sie ein- oder zweistellig, so lese man die Teilbarkeit bzw. Nichtteilbarkeit durch $7$ direkt ab. Anderenfalls verkleinere man sie mittels des gegebenen Verfahrens so lange, bis sie kleiner als $100$ ist oder auf einen Blick als nicht durch $7$ teilbar zu erkennen ist (z.B. $5678$). Da die Anzahl der Stellen in jedem Schritt um mindestens $1$ abnimmt, ist die Laufzeitschranke ebenfalls sofort einzusehen.