Teilbarkeitsregeln
Die Kongruenzregeln erlauben elegante Beweise der klassischen Teilbarkeitsregeln für Dezimalzahlen und allgemeiner für b-adische Darstellungen. Wir erinnern zunächst an:
Definition (b-adische Darstellung einer natürlichen Zahl)
Sei b ≥ 2. Weiter seien k ≥ 0 und z0, …, zk ∈ { 0, …, b − 1 }. Dann setzen wir
(zk … z0)b = zk bk + … + z0 b0.
Gilt n = (zk … z0)b, so heißt die Ziffernfolge zk … z0 die b-adische Darstellung von n.
Ist b fest gewählt, so schreiben wir auch kurz zk … z0 statt (zk … z0)b. Für b = 10 entspricht dies der üblichen Dezimalschreibweise für natürliche Zahlen.
Die eindeutige b-adische Darstellung einer natürlichen Zahl n erhalten wir induktiv durch Division mit Rest mit dem Divisor b. Ist
n = q b + r mit 0 ≤ r < b,
so ist n = (zk … z1 r)b, wobei zk … z1 die eindeutige b-adische Darstellung von q ist.
Beispiel
(10101)2 = 24 + 22 + 20 = 21, (10101)3 = 34 + 32 + 30 = 91,
(66666)7 = 6 · 74 + … + 6 · 70 = 6 75 − 17 − 1 = 75 − 1 = 16806,
wobei wir die für alle q ∈ ℝ mit q ≠ 1 gültige geometrische Summenformel 1 + … + qn = (qn + 1 − 1)/(q − 1) verwenden.
Nach diesen Vorbereitungen zeigen wir nun:
Satz (Quersummenregel der Division durch 3)
Eine natürliche Zahl n = (zk … z0)10 in Dezimaldarstellung ist genau dann durch 3 teilbar, wenn ihre Quersumme qs(n) = z0 + … + zk durch 3 teilbar ist. Genauer haben n und qs(n) bei Division durch 3 denselben Rest, d. h. es gilt n ≡ qs(n) (3).
Beweis
Es gilt 10m ≡ 1 (3) für alle m ≥ 1. Damit gilt nach den Kongruenzregeln
n = zk 10k + … + z0 100 ≡ zk 1 + … + z0 1 ≡ qs(n) (3).
Weitere Teilbarkeitsregeln diskutieren wir in den Übungen.