Bei Wer wird Millionär gab es neulich eine schöne kleine Frage, über die Günther Jauch sichtlich nachdenken musste: „Eine Zahl ist immer dann ohne Rest durch \(4\) teilbar, wenn die aus ihren letzten beiden Ziffern gebildete Zahl …?" – und genau hier muss man kurz mathematisch denken, statt sich von den hübschen Ablenkern locken zu lassen. Denn während Antworten wie „gerade ist“, „eine \(0\) enthält“ oder „die Quersumme \(4\) ergibt“ auf den ersten Blick plausibel klingen, steckt hinter der richtigen Antwort eine einfache Eigenschaft unseres Dezimalsystems.
Eine Zahl \(X\) ist genau dann durch \(4\) teilbar, wenn die aus ihren letzten beiden Ziffern gebildete Zahl durch \(4\) teilbar ist. Der Beweis folgt unmittelbar aus der Dezimaldarstellung. Jede natürliche Zahl \(X\) lässt sich eindeutig in der Form
\[
X = 100 \cdot X' + X''
\]
schreiben, wobei \(X''\) die aus den letzten beiden Ziffern gebildete Zahl ist, also \(0 \leq X'' < 100\), und \(X'\) der davorstehende Zahlenteil. Da
\[
100 = 25 \cdot 4
\]
gilt, folgt
\[
X = 25 \cdot 4 \cdot X' + X''.
\]
Der erste Summand \(25 \cdot 4 \cdot X'\) ist unabhängig von \(X'\) stets durch \(4\) teilbar. Für den Rest von \(X\) bei Division durch \(4\) ist daher ausschließlich \(X''\) relevant. Formal ausgedrückt:
\[
X \equiv X'' \pmod{4}.
\]
Damit gilt insbesondere:
\[
4 \mid X \iff 4 \mid X''.
\]
Ähnliche Teilbarkeitsregeln entstehen immer dann, wenn eine Potenz von \(10\) modulo einer Zahl besonders einfach wird. Bei der Teilbarkeit durch \(4\) war entscheidend, dass \(100 \equiv 0 \pmod 4\) gilt. Noch interessanter wird es, wenn statt \(0\) die Werte \(1\) oder \(-1\) auftreten.
Ein klassisches Beispiel ist die Teilbarkeit durch \(11\). Da
\[
10 \equiv -1 \pmod{11}
\]
gilt, wechseln die Stellenwerte einer Dezimalzahl modulo \(11\) immer zwischen \(1\) und \(-1\). Für
\[
X = a_0 + 10a_1 + 10^2a_2 + 10^3a_3 + \dots
\]
folgt daher
\[
X \equiv a_0 - a_1 + a_2 - a_3 + \dots \pmod{11}.
\]
Eine Zahl ist also genau dann durch \(11\) teilbar, wenn ihre alternierende Quersumme durch \(11\) teilbar ist. Bei \(918082\) erhält man etwa
\[
2 - 8 + 0 - 8 + 1 - 9 = -22,
\]
und da \(-22\) durch \(11\) teilbar ist, ist auch \(918082\) durch \(11\) teilbar.
Noch schöner ist die Regel für \(7\), \(11\) und \(13\) zugleich. Es gilt nämlich
\[
1001 = 7 \cdot 11 \cdot 13
\]
und damit
\[
1000 \equiv -1 \pmod{7}, \qquad
1000 \equiv -1 \pmod{11}, \qquad
1000 \equiv -1 \pmod{13}.
\]
Teilt man eine Zahl von rechts nach links in Dreierblöcke auf, darf man diese Blöcke deshalb abwechselnd addieren und subtrahieren. Für
\[
X = 123456789
\]
betrachtet man also
\[
789 - 456 + 123 = 456.
\]
Die ursprüngliche Zahl hat modulo \(7\), \(11\) und \(13\) denselben Rest wie \(456\). Damit kann eine sehr große Zahl durch eine wesentlich kleinere ersetzt werden, ohne die Teilbarkeit durch diese drei Zahlen zu verändern.
Auch die Teilbarkeit durch \(37\) besitzt eine überraschend elegante Form. Da
\[
999 = 27 \cdot 37
\]
gilt, ist
\[
1000 \equiv 1 \pmod{37}.
\]
Bei der Teilbarkeit durch \(37\) darf man daher die Dreierblöcke einfach addieren. Beispielsweise wird aus
\[
99937
\]
die Summe
\[
99 + 937 = 1036.
\]
Da
\[
1036 = 28 \cdot 37
\]
ist, ist auch \(99937\) durch \(37\) teilbar.
Solche Regeln wirken zunächst wie Zahlentricks, sind aber letztlich nur Anwendungen derselben Idee: Man ersetzt hohe Zehnerpotenzen durch einfache Reste modulo der gesuchten Zahl. Aus einer großen Dezimalzahl wird dadurch eine kleine Rechnung mit Kongruenzen. Genau deshalb sind solche Teilbarkeitsregeln mehr als bloße Rechentricks, nämlich die Reduktion auf Reste modulo \(10^k\): Sie wirken im Quizformat wie kleine Denkfallen, führen aber direkt zu einer erstaunlich eleganten Idee der Zahlentheorie.