Teilbarkeiten


Eine erste Anwendung des Begriffes "Teilbarkeit" findet sich in der Bruchrechnung, wenn bei Addition und Subtraktion ungleichnamiger Brüche ein kleinster gemeinsamer Nenner zu suchen ist und dieser mit Hilfe einer Primfaktorenzerlegung ermittelt werden soll. In diesem Fall richtet sich das Hauptaugenmerk auf die Eigenschaft, ob eine bestimmte Zahl durch eine andere Zahl teilbar ist, d.h. ob bei der Division ein Rest übrig bleibt.

Weitere Anwendungsgebiete des Begriffes "Teilbarkeit" wie Wochentagsermittlung, Berechnung des Osterdatums oder Ver- und Entschlüsseln von Botschaften beschäftigen sich mit der Beantwortung der Frage, welcher Rest bei der Division zweier Zahlen verbleibt.
Zu diesem Zweck wurde eine eigene Schreibweise, die der Problemstellung angepasst ist, entwickelt.
Anstelle der Aussage "153 läßt bei Division durch 19 den Rest 1." 153 ≡ 1 (19) (in Worten: 153 kongruent 1 modulo 19)

Der Ausdruck 1 (19) bedeutet aber umgekehrt nicht zwangsläufig die Zahl 153, denn es gibt unendlich viele ganzen Zahlen, die bei der Division durch 19 den Rest 1 ergeben (20, 39, 58, ..., aber auch -18, -37, -56, ...).
1 (19) bezeichnet somit eine ganze Klasse von Zahlen, nämlich alle ganzzahligen Vielfachen des Moduls (Teilers) 19, zu denen 1 addiert wird. Der Ausdruck 1 (19) wird deshalb als Restklasse 1 modulo 19 bezeichnet. Beim Modul 19 gibt es insgesamt 19 verschiedene Restklassen 0 (19), 1 (19), ..., 18 (19), die bei der Division durch 19 die Reste 0 bis 18 ermöglichen (ein Rest 19 entspricht ja wieder dem Rest 0 usw.).

Eine erste Anwendung der Restklassentheorie findet man in den nicht selten verwendeten Teilbarkeitsregeln.
Um derartige Teilbarkeitsregeln aufzustellen, werden die einzelnen Stellenwerte des verwendeten Zahlensystems auf die Reste in Bezug auf ein bestimmtes Modul untersucht.
Die folgenden Ausführungen beziehen sich auf das Dezimalsystem, weshalb für die Überprüfung bzw. Entwicklung von Teilbarkeitsregeln die einzelnen Zehnerpotenzen untersucht werden.
Eine erste Übersicht zeigt die Richtigkeit der Teilbarkeitsregeln für die Teiler 5, 10 und 100

Stellenwert HT ZT T H Z E
Rest bei Teiler 5 0 0 0 0 0 1
Rest bei Teiler 10 0 0 0 0 0 1
Rest bei Teiler 100 0 0 0 0 0 1

Für die Teiler 5 und 10 gelten 1 ≡ 1 (5) bzw. 1 ≡ 1 (10), 10 ≡ 0 (5) bzw. 10 ≡ 0 (10), 100 ≡ 0 (5) bzw. 100 ≡ 0 (10) usw.

Folglich ist die Teilbarkeit durch 5 bzw. durch 10 allein durch die Einerstelle bestimmt, alle anderen Stellen scheiden aufgrund eines nicht verbleibenden Restes aus (bekanntlich muß die Einerstelle beim Teiler 5 "0 oder 5" und beim Teiler 10 "0" sein).
Für den Teiler 100 gilt 1 ≡ 1 (100), 10 ≡ 10 (100) und 100 ≡ 0 (100).
Die Teilbarkeit durch 100 wird demnach durch Zehner- und Einerstelle bestimmt (sind beide "0", so ist die Zahl bekanntlich durch 100 teilbar).

Die letzten beiden Stellen sind auch für die Teilbarkeit durch 4 entscheidend, wie die folgende Tabelle für einige Zweierpotenzen als Teiler zeigt:

Stellenwert HT ZT T H Z E
Rest bei Teiler 2 0 0 0 0 0 1
Rest bei Teiler 4 0 0 0 0 2 1
Rest bei Teiler 8 0 0 0 4 2 1
Rest bei Teiler 16 0 0 8 4 2 1

Eine beliebige natürliche Zahl ist also genau dann durch 2 teilbar, wenn die Einerstelle durch 2 teilbar, d.h. gerade bzw. 0 ist.
Für die Teilbarkeit durch 4 = 22 sind die letzten 2, für die Teilbarkeit durch 8 = 23 die letzten 3 Stellen ... entscheidend.

Aufgrund der Tabelle liegt auch dann eine Teilbarkeit durch 4 vor, wenn die Summe aus dem zweifachen Wert der Zehnerziffer und dem einfachen Wert der Einerziffer durch 4 teilbar ist (so ist etwa die Zahl 123456 durch 4 teilbar, da 2.5 + 1.6 = 16 durch 4 teilbar ist).

Eine interessante Tabelle erhält man für die Teiler 3 und 9:

Stellenwert HT ZT T H Z E
Rest bei Teiler 3 1 1 1 1 1 1
Rest bei Teiler 9 1 1 1 1 1 1

Hier muß zwar jede Dezimalstelle berücksichtigt werden, allerdings liefert jede Dezimalstelle bei Division durch 3 bzw. 9 den Rest 1, weshalb für die Überprüfung der Teilbarkeit jede Stelle mit ihrem einfachen Wert gewichtet werden kann.

Es gilt also: Eine natürliche Zahl ist genau dann durch 3 bzw. durch 9 teilbar, wenn die Summe ihrer Ziffern (Ziffern- oder Quersumme) durch 3 bzw. durch 9 teilbar ist.

Auch bei der Teilbarkeit durch 11 können Quersummen verwendet werden.
Es gilt nämlich:

Stellenwert HT ZT T H Z E
Rest bei Teiler 11 − 1 1 − 1 1 − 1 1

In diesem Fall wird eine alternierende Quersumme, bei der die einzelnen Ziffern abwechselnd addiert und subtrahiert werden, gebildet.
Ist diese Quersumme gleich 0 oder ein Vielfaches von 11, so ist die Zahl durch 11 teilbar.

Mit Hilfe von derartigen Tabellen kann für jede (!) natürliche Zahl eine Teilbarkeitsregel entwickelt werden.
Insbesondere erhält man für den Teiler 7 die Tabelle:

Stellenwert HT ZT T H Z E
Rest bei Teiler 7 5 4 6 2 3 1
oder − 2 − 3 − 1 2 3 1

Zehnerpotenzen sind nicht durch 7 teilbar, zusätzlich treten alle Restklassen außer 0 (7) auf.
Die Stellenwerte der zu prüfenden Zahl müssen daher der Reihe nach mit 1, 3, 2, 6, 4, 5, ... (oder 1, 3, 2, -1, -3, -2, ...) multipliziert und anschließend addiert werden.
Ist diese Summe 0 oder ein Vielfaches von 7, so ist die Zahl durch 7 teilbar.
Meist ist jedoch bei diesem Teiler der direkte Teilungsversuch kürzer als die Anwendung der Teilbarkeitsregel.

Viele Teilbarkeistregeln können aus der Kombination zweier oder mehrerer Teilbarkeitsregeln entwickelt werden.
So ist etwa eine natürliche Zahl genau dann durch 12 (= 3 ⋅ 4) teilbar, wenn sie durch 3 und durch 4 teilbar ist.
Beispiel: 84 ≡ 0 (3) und 84 ≡ 0 (4), so gilt: 84 ≡ 12 (5).

Eine natürliche Zahl ist jedoch nicht unbedingt durch 12 (= 2 ⋅ 6) teilbar, wenn sie durch 2 und durch 6 teilbar ist.
Es gilt zwar 24 ≡ 0 (2), 24 ≡ 0 (6) und zugleich auch 24 ≡ 0 (12),
aber aus 30 ≡ 0 (2) und 30 ≡ 0 (6) folgt nicht (!) 30 ≡ 0 (12).

Allgemein gilt: Ist eine natürliche Zahl sowohl durch den Faktor a als auch durch den Faktor b teilbar, so ist sie mit absoluter Sicherheit auch dann durch das Produkt a ⋅ b teilbar, wenn a und b teilerfremd sind, also ggT(a, b) = 1 gilt.

Je größer der Teiler wird, desto größer wird auch die mögliche Anzahl verschiedener Reste.
Deshalb werden die Teilbarkeitsregeln allmählich komplizierter, sodaß es schließlich einfacher ist, den direkten Teilungsversuch zu unternehmen als die entsprechende Teilbarkeitsregel anzuwenden.
Eine Ausnahme bilden nur noch spezielle Teiler wie 25 oder Zehnerpotenzen.
Für den Teiler 25 gilt:

Stellenwert HT ZT T H Z E
Rest bei Teiler 25 0 0 0 0 10 1

Die Teilbarkeit einer Zahl durch 25 ist also genau dann gewährleistet, wenn die letzten beiden Stellen durch 25 teilbar sind.

Eine äußerst praktische − und auch wichtige − Anwendung von Restklassen findet sich bei der österreichischen Sozialversicherungsnummer.
Jede österreichische Sozialversicherungsnumme besteht aus insgesamt 10 Ziffern.
Dabei stellen die ersten drei Ziffern eine laufende Nummer dar, während die letzten sechs Ziffern das Geburtsdatum in der Form TTMMJJ wiedergeben.
Die dazwischen liegende vierte Ziffer ist eine Prüfziffer und soll mögliche Übertragungsfehler vermindern bzw. vermeiden.
Für die Ermittlung der Prüfnummer werden die drei Stellen der laufenden Nummer und die sechs Stellen des Geburtsdatums von links nach rechts mit den Faktoren 3, 7, 9, 5, 8, 4, 2, 1 und 6 multipliziert und die jeweiligen Produkte addiert.
Die Prüfziffer ist jener Rest, wenn die Gesamtsumme durch 11 dividiert wird (da das Modul 11 sowohl die Restklasse 0 als auch die Restklasse 10 besitzt, wird bei einem möglichen Rest 10 die laufende Nummer nicht vergeben).