Teilbarkeitsregeln (Anwendung der Kongruenzrechnung)

In der Restklasse ${\left[0\right]}_{m}mitm\in \mathbb{Z}undm>0$ liegen alle ganzen Zahlen, die Vielfache von m sind. Deshalb kann man die Teilbarkeitsrelation in $\mathbb{Z}$ mithilfe der Kongruenz wie folgt definieren:
$m|a\iff a\equiv 0\left(m\right)$

In der Menge der Restklassen modulo m werden eine Addition und eine Multiplikation erklärt, die sich auf die Operationen der Repräsentanten stützen, aber nicht von der Wahl der Repräsentanten abhängig sind:
$\begin{array}{c}{\left[a\right]}_m+{\left[b\right]}_m=\left[a+b\right]{}_m\\ {\left[a\right]}_m\cdot {\left[b\right]}_m={\left[a\cdot b\right]}_m(\ast )\end{array}$
Diese wichtige Eigenschaft der Restklassen bildet die Grundlage für die Beweise der im Folgenden angeführten Teilbarkeitsregeln.

• Satz: Es sei $z=a_k{a}_{k-1}\mathrm{...}{a}_1{a}_0=a_k\cdot {10}^k+a_{k-1}\cdot {10}^{k-1}+\mathrm{...}+a_1\cdot 10+a_0$ mit $0\le a_{\nu }\le 9$ und $\nu =\mathrm{0,}\mathrm{1,}\mathrm{...,}k.$
  Dann gilt:
  (1) $2|zbzw.4|zbzw.8|z$ genau dann, wenn $2|a_{0}bzw.4|a_1{a}_{0}bzw.8|a_2{a}_1{a}_0$ mit $a_1{a}_0=10\cdot a_1+a_0$ und $a_2{a}_1{a}_0=100a_2+10a_1+a_0$.
  (2) $3|zbzw.9|z$ genau dann, wenn $3|Qbzw.9|Q$ (wobei $Q=a_0+a_1+\mathrm{...}+a_{k-1}+a_k$ die Quersumme von z ist)
  (3) $11|z$ genau dann, wenn $11|Q\text{'}$ (wobei $Q\text{'}=a_0-a_1+a_2-\mathrm{...}+{\left(-1\right)}^k{a}_k$ die alternierende Quersumme von z ist)

Da $m|a$ mit $a\equiv 0\left(m\right)$ gleichwertig ist, ergeben sich die genannten Teilbarkeitsregeln aus den entsprechenden Kongruenzen.
Beweis von (1):
Aus $10\equiv 0\left(2\right)$ folgt ${\left({\left[10\right]}_2\right)}^2={\left[10\right]}_2\cdot {\left[10\right]}_2={\left[0\right]}_2\cdot {\left[0\right]}_2={\left[0\right]}_2$ nach $(\ast )$ und damit ${10}^{\nu }\equiv 0\left(2\right)für\nu \ge 1$, d.h.:
$\begin{array}{c}{\left[z\right]}_2={\left[a_k\cdot {10}^k\right]}_2+\mathrm{...}+{\left[a_1\cdot 10\right]}_2+{\left[a_0\right]}_2\\ ={\left[a_k\right]}_2\cdot {\left[{10}^k\right]}_2+\mathrm{...}+{\left[a_1\right]}_2\cdot {\left[10\right]}_2+{\left[a_0\right]}_2\\ ={\left[a_k\right]}_2\cdot {\left[0\right]}_2+\mathrm{...}+{\left[a_1\right]}_2\cdot {\left[0\right]}_2+{\left[a_0\right]}_2\\ ={\left[a_0\right]}_2\end{array}$
Das ist gleichbedeutend mit $z\equiv a_0\left(2\right).$
Ganz analog erhält man aus ${10}^2\equiv 0\left(4\right)$ die Relation ${10}^{\nu }\equiv 0\left(4\right)für\nu \ge 2$ und damit $z=a_k\cdot {10}^k+a_{k-1}\cdot {10}^{k-1}+\mathrm{...}+a_1\cdot 10+a_0\equiv \left(a_1\cdot 10+a_0\right)\mathrm{mod}4.$
Aus ${10}^3\equiv 0\left(8\right)$ folgt ${10}^{\nu }\equiv 0\left(8\right)für\nu \ge 3$ und damit $z\equiv \left(a_2\cdot {10}^2+a_1\cdot 10+a_0\right)\mathrm{mod}8.$

Beweis von (2):
$z\equiv Q\left(3\right)$, da aus ${10}^0\equiv 1\left(3\right)und{10}^1\equiv 1\left(3\right)$ die Relation ${10}^{\nu }\equiv 1\left(3\right)für\nu \ge 0$ folgt.
Gleiches gilt für die Kongruenz modulo 9.

Beweis von (3):
$z\equiv Q\text{'}\left(11\right)$, da aus ${10}^0\equiv 1\left(11\right)und{10}^1\equiv -1\left(11\right)$ die Relationen ${10}^{\nu }\equiv -1\left(11\right)für\nu =\mathrm{1,}\mathrm{3,}\mathrm{5,}\mathrm{...}$ und ${10}^{\nu }=1\left(11\right)für\nu =\mathrm{2,}\mathrm{4,}\mathrm{6,}\mathrm{...}$ folgen.

Die Teilbarkeitsregeln für 9 und 11 können auch für Rechenkontrollen angewendet werden. Da $ggT\left(\mathrm{9,}11\right)=1$ ist, folgt aus $a\equiv b\left(99\right)$, dass $a\equiv b\left(9\right)unda\equiv b\left(11\right)$ ist. Das wird im Folgenden an zwei Beispielen demonstriert.
Anmerkung: Natürlich kann man statt 9 und 11 auch 2 und 3 oder 3 und 7 wählen, aber um eine Gleichheit zu überprüfen ist die Wahrscheinlichkeit größer, wenn sie bis auf Vielfache von 99 statt bis auf Vielfache von 6 oder 21 übereinstimmt.

Beispiel 1: $54729\cdot 543=29717847$

Neunerprobe:
$\begin{array}{c}54729\cdot 543\equiv \left(5+4+7+2+9\right)\cdot \left(5+4+3\right)\equiv 0\cdot 3\equiv 0\left(9\right)\\ 29717847\equiv \left(2+9+7+1+7+8+4+7\right)\equiv 0\left(9\right)\end{array}$
Elferprobe:
$\begin{array}{c}54729\cdot 543\equiv \left(9-2+7-4+5\right)\cdot \left(3-4+5\right)\equiv 15\cdot 4\equiv 4\cdot 4\equiv 5\left(11\right)\\ 29717847\equiv \left(7-4+8-7+1-7+9-2\right)\equiv 5\left(11\right)\end{array}$
Es ist mit großer Wahrscheinlichkeit anzunehmen, dass richtig gerechnet wurde.

Beispiel 2: $477773\cdot 535353=259778208869$

Neunerprobe:
$\begin{array}{c}477773\cdot 535353\equiv \left(4+7+7+7+7+3\right)\cdot \left(5+3+5+3+5+3\right)\\ \equiv 35\cdot 24\equiv 8\cdot 6\equiv 3\left(9\right)\\ 259778208869\equiv \left(2+5+9+7+7+8+2+0+8+8+6+9\right)\\ \equiv 71\equiv 8\left(9\right)\end{array}$
Wegen ${\left[3\right]}_9\ne {\left[8\right]}_9$ wurde hier mit Sicherheit falsch gerechnet.

Die Kongruenzrechnung ist auch ein wichtiges Hilfsmittel für die Kalenderrechnung, worauf hier nicht näher eingegangen werden wird. Aber die Tatsache, dass sich im Normalfall (kein Schaltjahr) der zu einem Datum gehörende Wochentag von Jahr zu Jahr um einen Tag verschiebt, ist aus der Kongruenzrechnung offensichtlich, da $365\equiv 1\left(7\right)$ ist.