Es gibt ganz einfache Regeln zur Teilbarkeit. Die für 2, 3 und 5 kennt wohl jeder. Und dass man sich nur die Regeln für Primzahlen merken muss, ist auch klar, denn letztlich sind auch die Teiler aus Primfaktoren zusammengesetzt.
Wie leitet man sich nun Regeln für die Teilbarkeit durch andere Primzahlen her? Man kann die Zahl verkleinern, sodass es besser sichtbar wird, ob sie den Teiler hat. Die Grundidee dabei ist, dass man bezüglich der Teilbarkeit Teile subtrahieren darf, von denen man sicher weiß, dass sie teilbar sind. Wenn z.B. die Teilbarkeit durch 7 gefragt ist, kann ich von 7654 einfach 7000 abziehen und muss nur noch 654 genauer betrachten. Untersuchen wir hier ein „Schema-F“, welches ohne Fallunterscheidungen auskommt:
Teile die Zahl n als Summe aus ihrer Einerstelle b und den restlichen a auf:
$$ n = 10 a + b $$
Multipliziere diesen Ausdruck mit einer Zahl k, die nicht den zu prüfenden Teiler t enthalten darf und die den Term mit dem a auf einen Wert bringt, der auf +1 oder -1 von einer Zahl abweicht, die den Teiler t hat.
Das bedeutet umgekehrt, dass die Einerstelle von 10 k a +/- 1 eine 1 oder 9 sein muss. Betrachten wir jetzt die Teiler 2 und die 5 gesondert und ansonsten wie oben gesagt, nur Primzahlen, dann ergibt sich, dass das entweder schon beim Teiler selbst der Fall ist, wenn er eben als Einerstelle eine 1 oder 9 hat, oder aber beim Dreifachen des Teilers, wenn er als Einerstelle eine 3 oder 7 hat.
Nehmen wir ab hier ein konkretes Beispiel und prüfen auf die Teilbarkeit durch t=7 und wählen als Faktor k die 2.
$$ 20 a + 2 b $$
Nun addieren wir ein a, erhalten so 21 a, welches durch 7 teilbar ist und daher als Summe nicht mehr betrachtet werden muss. Hinten beim b ziehen wir zum Ausgleich ein a wieder ab. Da die Teilbarkeit für positive und negative Zahlen gleich ist und das a typischerweise größer als 2b ist, können wir die beiden auch vertauschen, um positive Zahlen zu erhalten.
$$ 21 a − a + 2 b $$
Die 21a wird also nicht weiter betrachtet, weil sie durch 7 teilbar ist und der Rest mal -1 genommen:
$$ a − 2 b $$
Dieses Schema a – 2b kann man so lange wiederholen, bis die Zahl klein genug geworden ist, um direkt zu sehen, ob sie die 7 als Teiler hat. Die zu prüfende Zahl wird also bei jedem Schritt ca. um den Faktor 10 kleiner, sodass sie schließlich im Bereich des kleinen Einmaleins liegt.
Konkrete Beispiele
- 2415
241 – 2*5 = 231
23 – 2 = 21 ist durch 7 teilbar
- 3698
369 – 16 = 353
35 – 6 = 29 ist nicht durch 7 teilbar
Anschaulich gesagt, haben wir uns hier Regeln hergeleitet, nach denen die 2415 genau dann durch 7 teilbar ist, wenn es die 231 auch ist und die nun wieder ist genau dann teilbar, wenn es die 21 auch ist.
Teilbarkeit durch 13
So ähnlich kann man sich auch für andere Zahlen Teilbarkeitsregeln herleiten, die einfach auf der Verkleinerung der ursprünglichen Zahl beruhen. Hier noch als ein Beispiel für die Teilbarkeit durch 13 mit dem Faktor 4 wobei die 39 durch 13 teilbar ist:
$$ \begin{align}
n & = 10 a + b \ \ \ \ && \big \vert * 4 \\
4 n & = 40 a + 4 b \\
& = 39 a + ( 4 b + a ) \ \ \ \ && \big \vert − 39 a \\
4 n − 39 a & = a + 4 b \\
\end{align} $$
Die Zahl n hat auch mit k=4 multipliziert immer noch die gleiche Teilbarkeit und die − 39 a ändert an der Teilbarkeit durch t=13 nichts, weil der Term selber durch 13 teilbar ist. Also ist a+4b ein Rechenschema für die Teilbarkeit durch 13.
Verallgemeinerung
Allgemein gesagt wählt man das k also immer so, dass der Faktor (10 k +/- 1) des vorderen Terms mit a durch t teilbar ist und nicht betrachtet werden muss. Dabei darf die Teilbarkeit nicht durch den Faktor k entstehen. Sonderfälle sind hier die 2 und die 5. Die stecken gewissermaßen schon im ersten Faktor 10 drin. Daher muss man wie wohl schon bekannt bei der Teilbarkeit durch 2 und 5 nur die Einerstelle betrachten.
$$ \begin{align}
n = \ & 10a + b \ \ \ \ && \big \vert * k \\
& 10 k a + k b \\
& (10 k \pm 1) a \mp a + k b \ \ \ \ && \big \vert − (10 k \pm 1) a \\
& a \mp k b
\end{align} $$
Für die 3 ergibt sich als Schema einfach a+b, was iterativ angewendet eben genau die Quersumme ergibt.
Wer mag, kann sich das für die Teilbarkeit durch 11 herleiten, welche nach diesem Schema eine ähnlich einfache Regel ergibt.
Der Trick besteht also zusammengefasst darin, einen großen Anteil der Zahl zu subtrahieren, der garantiert teilbar ist und mit diesem Teil selbst nicht viel rechnen zu müssen und im Verlaufe des Algorithmus keine Fallunterscheidungen machen zu müssen.
Sinn des Ganzen
Der große Vorteil dieser mathematisch sauber hergeleiteten Regeln gegenüber dem „Ausprobieren“ durch Teilen ist, dass ich hier nur mathematische Methoden auf Ganzzahlen benutze, die garantiert keine Rundungsfehler enthalten. Falls beim Programmieren oder auf dem Taschenrechner nämlich die Anzahl der Stellen in der Mantisse der Fließkommazahlen kleiner ist als die Anzahl der Stellen meiner Ganzzahlen, werde ich nach dem testweisen Dividieren gar nicht mehr sehen, ob es glatt aufgegangen ist. Beim Programmieren wird man daher nicht die Division benutzen, sondern mit Modulo rechnen.
Das ist übrigens ein genereller Tipp: Den Überlauf (engl. Overflow) haben die meisten Programmierer im Sinn; zumal er in vielen Programmiersprachen auch einen Fehler erzeugt. Aber es gibt auch den „Unterlauf“ oder englisch Underflow. Damit ist gemeint, dass Nachkommastellen so klein werden, dass sie zu 0 gerundet werden. Das ist ein Fehler, der leicht übersehen werden kann.
Ein konkretes Beispiel dazu. Nehmen wir an, wir haben einen Datentyp mit einer 6-stelligen Mantisse gewählt und wir wollen die Teilbarkeit durch 23 prüfen. Für 234578 werden wir hier falsche Ergebnisse erhalten, denn die Nachkommastellen können in 6 Stellen nicht angezeigt werden. Rechnen wir dagegen mit Modulo, erhalten wir das korrekte Ergebnis: Rest 1.
Die meisten dieser Teilbarkeitsregeln sind für manuelle Anwendung gedacht. Man kann sie natürlich programmieren. Betrachtet man jedoch die „Kosten“ im Sinne des Rechenaufwands wird man größtenteils feststellen, dass sie in Summe mindestens ebenso „teuer“ sind wie das Modulo. Eines der Probleme ist, dass die Betrachtung von „Stellen“ eine String-Operation ist. Man muss die Zahl also zwischen ihrer numerischen Darstellung und ihrer textuellen umwandeln.
Ein anderer Aspekt ist, dass man beim schriftlichen Dividieren ebenso exakt arbeitet und ähnlich viel Aufwand hat, dann aber eben ein „richtiges“ Ergebnis hat. Man könnte also ketzerisch sagen, diese Teilbarkeitsregeln dienen nur dazu, Schüler in der Schule zu ärgern, da das Ganze in der Praxis wenig Anwendung hat. 😜
