Teilbarkeitsregeln

In diesem Artikel soll es um Regeln gehen, wie man entscheidet, ob eine Zahl durch 2, 3, 5, 7, 11 oder 13 teilbar ist. Dabei geht vor allem auch darum, zu verstehen und zu beweisen, warum diese Regeln funktionieren. Falls die Teilbarkeit nicht gegeben ist, interessieren wir uns für den Rest, der bei der Division verbleibt.

Was heißt überhaupt Teilbarkeit?

Im ganzen Artikel betrachten wir nur ganze Zahlen, es geht also zunächst darum, wann eine ganze Zahl a durch eine ganze Zahl b teilbar ist.

Eine ganze Zahl a ist durch eine ganze Zahl b teilbar, wenn eine ganze Zahl n existiert, sodass a=b \cdot n gilt. Wir schreiben dann auch b \mid a.

Zum Beispiel ist gilt 3\mid 9, weil wir n=3 wählen können. Jede ganze Zahl a ist durch 1 teilbar, also 1 \mid a, weil wir n=a wählen können. Wenn wir das Vorzeichen von a oder b ändern, so bleibt auch die Teilbarkeit erhalten, weil auch das Vorzeichen von n geändert werden kann. Zum Beispiel ist 8 durch -2 teilbar. Nach dieser Definition ist außerdem 0\mid 0, als n kann jede beliebige Zahl gewählt werden. Teilbarkeit heißt also nicht unbedingt, dass die Division \frac ab aufgehen muss.

Im allgemeinen Fall können wir a=b\cdot n + r schreiben, wobei 0~\leq~r~\lt~b gelten soll. Dann ist r der Rest, der bei Division von a durch b entsteht. Wir subtrahieren (oder addieren falls a \lt 0 ) so oft b, bis wir zwischen 0 und b landen. Zum Beispiel ist der Rest bei der Division von 7 durch 3 gleich 1, weil 7 = 2 \cdot 3 + 1.

Außerdem interessieren wir uns für den Fall, dass zwei Zahlen x und y den gleichen Rest bei Division durch n lassen. Man kann sich überlegen, dass das genau dann der Fall ist, wenn die Differenz x-y durch n teilbar ist. Wir schreiben dann auch x \equiv y \mod n, gesprochen „x ist kongruent y modulo n. Zum Beispiel gilt 2 \equiv 12 \mod 5, weil 12-2=10 durch 5 teilbar ist. Diese Notation wird beim Begründen der Teilbarkeitsregeln sehr helfen.

Unter der Voraussetzung, dass x \equiv y \mod n gilt, kann man schlussfolgern:

• Für jede ganze Zahl z gilt x + z \equiv y+z \mod n
• Für jede ganze Zahl a gilt a\cdot x \equiv a \cdot y \mod n
• Für jede natürliche Zahl d gilt x^d \equiv y^d \mod n

Die erste Aussage folgt daraus, dass die Differenz sich nicht geändert hat und damit immer noch durch n teilbar sein muss. Bei der zweiten Aussage ist die Differenz a(x-y). Das ist ein Vielfaches von x-y, was wiederum durch n teilbar ist. Die Teilbarkeit bleibt also erhalten, weil wir das n in der Definition der Teilbarkeit auch mit a multiplizieren können.

Die letzte Aussage ist nicht mehr ganz so einfach zu beweisen, dafür aber umso nützlicher. Wir nutzen aus, dass man x^d-y^d allgemein faktorisieren kann. Es gilt nämlich x^d-y^d = (x-y)\left(x^{d-1}+x^{d-2}y+\cdots+xy^{d-2}+y^{d-1}\right)\;. Damit ändert sich auch hier die Teilbarkeit nicht, weil nur mit einem Faktor multipliziert wurde.

Außerdem verhält sich Kongruenz auch bei Umformungen ziemlich ähnlich zum Gleichheitszeichen. Zum Beispiel folgt aus x \equiv y \mod n und y \equiv z \mod n auch x \equiv z \mod n. Damit können wir also eine Umformungskette von Kongruenzen schreiben und folgern, dass Start und Ende zueinander kongruent sind.

Was sollen diese Definitionen bringen?

Wir können mitlerweile recht elegant gewisse Reste ausrechnen, was für die Teilbarkeitsregeln wichtig werden wird. Was ist zum Beispiel der Rest, der bei Division von 7^{42} durch 6 entsteht? Da 7 \equiv 1 \mod 6 können wir schreiben:

7^{42} \equiv 1^{42} = 1 \mod 6

Also haben wir einen Rest von 1.

Teilbarkeitsregel für 2

Diese Regel ist dir wahrscheinlich bekannt. Eine Zahl ist genau dann durch 2 teilbar, wenn die letzte Ziffer gerade ist. Bei Division durch 2 gibt es auch nur zwei mögliche Reste (nämlich 0 und 1). Wenn die letzte Ziffer ungerade ist, haben wir also einen Rest von 1.

Warum funktioniert das? Wir können unsere gegebene Zahl m schreiben als 10a+b, wobei b eine einstellige Zahl ist. Es gilt:

m=10a+b \equiv 0 \cdot a + b = b \mod 2

Der Rest bei Division von m durch 2 ist also der gleiche wie bei der Division der letzten Ziffer durch 2. Das entspricht aber gerade genau der Regel.

Schauen wir uns noch etwas allgemeiner Teilbarkeitsregeln für Zweierpotenzen 2^s an, wobei s eine natürliche Zahl ist. Hier ist die Regel, dass wir uns nur die letzten s Stellen der Zahl anschauen und dort den Rest bestimmen. Für s=1 entspricht das genau der Regel für 2. Die Teilbarkeitsregel für 4 ist also, sich die letzten beiden Stellen der Zahl anzuschauen.

In der Begründung gehen wir hier ähnlich vor. Wir schreiben m=10^s+b, wobei b den letzten s Stellen der Zahl entspricht. Da 2\mid 10 gilt, gilt auch 2^s\mid 10^s (wir finden n=5^2). Es folgt:

m = 10^s+b \equiv b \mod 2^s

Damit ist die Regel gezeigt. Im nächsten Artikel werden wir unter anderem die Teilbarkeitsregel für 16 benötigen, also die letzten vier Stellen betrachten.

Teilbarkeitsregel für 5

Auch diese hast du vermutlich schon eimal gesehen. Eine Zahl ist genau dann durch 5 teilbar, wenn die letzte Ziffer eine 0 oder eine 5 ist. Das ist aber wiederum genau dann der Fall, wenn die letzte Ziffer durch 5 teilbar ist. Wir kommen auf die gleiche Regel wie bei der 2, nur dass die 2 durch eine 5 ersetzt wird. Die Begründung funktioniert genauso, weil auch 5 die Eigenschaft hat, ein Teiler von 10 zu sein.

Auch die Verallgemeinerung läuft vollkommen analog. Eine Zahl ist durch 5^s teilbar, wenn die letzten s Stellen durch 5^s teilbar sind. Zum Beispiel lässt 52947534 bei Division durch 25 den Rest 9, weil 34 den Rest 9 lässt. Der Beweis ist genau der gleiche wie eben.

Teilbarkeitsregel für 3

Vielleicht ist dir diese Regel auch schon einmal begegnet, wahrscheinlich aber noch kein Beweis, warum man die Regel anwenden kann. Wir bestimmen die Quersumme, also die Summe der Ziffern, der gegebenen Zahl und schauen, ob diese durch 3 teilbar ist. Zum Beispiel ist 3283461 durch 3 teilbar, weil 3+2+8+3+4+6+1=27 durch 3 teilbar ist (auch hierfür können wir noch einmal auf 2+7=9 vereinfachen). Etwas allgemeiner stimmt der Rest mit dem Rest der Quersumme überein.

Zur Begründung schauen wir uns unsere Zahl als Summe von Zehnerpotenzen (mit Vorfaktoren) an. Zum Beispiel wollen wir 245=5 + 4 \cdot 10 + 2 \cdot 100 schreiben. Die Faktoren vor den Zehnerpotenzen sind dann genau die Ziffern unserer Zahl. Allgemein schreiben wir die Zahl m als

a_0 \cdot 10^0 + a_1 \cdot 10^1 + a_2 \cdot 10^2 + \cdots + a_k \cdot 10^k \;.

Die Zahl hat also die Ziffern a_k bis a_0. Nun verwenden wir, dass 10 \equiv 1 \mod 3, also 10^d \equiv 1^d = 1 \mod 3. Damit erhalten wir dann:

m \equiv a_0 \cdot 1 + a_1 \cdot 1 + \cdots + a_k \cdot 1 \mod 3

Das ist die Summe der Ziffern, also genau die Quersumme! Damit ist die Regel bewiesen.

Teilbarkeitsregel für 9

Für 9 funktioniert die Regel genauso wie für 3. Wir schauen uns nur den Rest der Quersumme bei Division durch 9 an. Die Begründung läuft vollkommen analog. Wir starten wieder mit der Darstellung als Summe von Zehnerpotenzen. Dann verwenden wir 10 \equiv 1 \mod 9 und können den gleichen Schluss ziehen. Man könnte vielleich auf die Idee kommen, dass man diese Regel allgemein für Dreierpotenzen anwenden könnte. Für 27 funktioniert das aber schon nicht mehr, zum Beispiel lässt 11 nicht den Rest 2, sondern den Rest 11. Das liegt daran, dass 10 \equiv 1 \mod 27 nicht gilt.

Teilbarkeitsregel für 11

Für 11 können wir etwas Ähnliches wie für 3 und 9 machen. Statt der Quersumme betrachten wir jetzt aber die sogenannte alternierende Quersumme. Wir beginnen mit der letzten Stelle und addieren und subtrahieren abwechselnd die weiteren Stellen. Die Zahl, die wir erhalten lässt dann den gleichen Rest. Bei 4529 rechnen wir 9-2+5-4=8, also lässt 4529 bei Division durch 11 den Rest 8. Bei 192 erhalten wir zunächst 2-9+1=-6. Also haben wir hier den Rest 5 (wegen -6 \equiv 5 \mod 11).

Auch hier schreiben wir wieder

m=a_0 \cdot 10^0 + a_1 \cdot 10^1 + a_2 \cdot 10^2 + \cdots + a_k \cdot 10^k \;.

Es ist 10 \equiv -1 \mod 11, also folgt 10^d \equiv (-1)^d \mod 11. Falls d gerade ist, erhalten wir eine 1, ansonsten eine -1.

Damit folgt:

m \equiv a_0 \cdot 1 + a_1 \cdot (-1) + a_2 \cdot 1 + \cdots + a_k \cdot (-1)^k \mod 11

Das entspricht allerdings genau der alternierenden Quersumme.

Teilbarkeitsregeln für 7 und 13

Diese Regeln sind nicht mehr ganz so bekannt, weil sie nicht mehr so einfach anzuwenden sind, wie zum Beispiel bei 9. Wir nutzen hier aus, dass 1001=7 \cdot 11 \cdot 13 ist. Dann gehen wir recht analog wie bei 11 vor, nur dass wir uns jetzt von hinten ausgehend Dreierblöcke von Ziffern anschauen. Zum Beispiel ist 2342941 = 941 \cdot 1000^0 + 342 \cdot 1000^1 + 2 \cdot 1000^2 \;. Wir berechnen die alternierende Summe dieser Dreierblöcke und kommen auf den gleichen Rest. Im Beispiel erhalten wir 941-342+2=601. Je nachdem, ob wir jetzt den Rest bei Division durch 7 oder durch 13 (oder auch durch 11) betrachten, können wir damit weiterrechnen.

Es verbleibt also meist eine dreistellige Zahl, mit der man noch weiterrechnen muss, was aber zumindest einfacher als eine siebenstellige Zahl ist. Die Begründung dieser Regel läuft wieder ziemlich analog zur 11, nur dass wir jetzt 1000 \equiv -1 \mod 1001 verwenden. Weil 1001 durch 7 und 13 teilbar ist, gilt dann natürlich auch 1000 \equiv -1 \mod 7 und 1000 \equiv -1 \mod 13.

Was ist zum Beispiel mit 6?

Wir haben bis jetzt nur Primzahlen und Potenzen von Primzahlen betrachtet. Im Wesentlichen reicht das auch aus, weil man eine Zahl in ihre Primfaktoren zerlegen kann und sich diese getrennt anschaut. Eine Zahl ist zum Beispiel durch 6 teilbar genau dann, wenn sie durch 2 und durch 3 teilbar ist. Hier ist wichtig, dass 2 und 3 keinen gemeinsamen Teiler außer 1 (und -1) haben.

Auch den Rest kann man durch die einzelnen Faktoren bestimmen. Dabei verwendet man den sogenannten Chinesischen Restsatz, der für diesen Artikel erst einmal zu weit gehen würde. Vielleicht wird er Gegenstand einer der folgenden Artikel werden. Im nächsten Artikel werden wir unter anderem Teilbarkeitsregeln für 16 und 11 anwenden und damit aufgehende Kubikwurzeln aus bis zu 12-stelligen Zahlen bestimmen.