Teilbarkeit

Grundbegriff und zentrale Eigenschaften

Teilbarkeit ist eine zweistellige Relation auf den ganzen Zahlen. Eine ganze Zahl a teilt eine ganze Zahl b genau dann, wenn es eine ganze Zahl n gibt mit a · n = b. Dann schreibt man a ∣ b; b heißt ein Vielfaches von a. Gilt dies nicht, schreibt man a ∤ b. Anschaulich geht die Division b : a ohne Rest auf: 8 ist durch 4 teilbar, weil 8 : 4 = 2, 9 dagegen nicht durch 4, weil der Rest 1 bleibt.

Die 0 ist ein Sonderfall: Jede Zahl a teilt 0, da a · 0 = 0. Außerdem ist 0 ein Teiler von sich selbst, obwohl die Division durch 0 im Allgemeinen nicht definiert ist. Die Einheiten des Rings ℤ der ganzen Zahlen sind 1 und −1; sie sind triviale Teiler jeder ganzen Zahl. Für b ≠ 0 heißen die übrigen Teiler, also neben ±1 und ±b, nichttriviale oder echte Teiler.

Eine ganze Zahl, die keine Einheit ist und nur triviale Teiler besitzt, heißt Primelement; ist sie größer als 1, nennt man sie Primzahl. Ein Primteiler oder Primfaktor von b ist ein Primteiler von b. Die Menge aller Teiler einer natürlichen Zahl n heißt Teilermenge, die Menge aller Vielfachen Vielfachenmenge. Die Teileranzahlfunktion ordnet n die Anzahl seiner Teiler zu.

Wichtige Eigenschaften sind:

Aus a ∣ b folgt −a ∣ b und a ∣ −b.
Aus a ∣ b und b ∣ c folgt a ∣ c (Transitivität).
Für k ∈ ℤ \ {0} gilt a ∣ b genau dann, wenn ka ∣ kb.
Aus a ∣ b und c ∣ d folgt ac ∣ bd.
Aus a ∣ b und a ∣ c folgt a ∣ kb + lc für alle k, l ∈ ℤ.
Aus a ∣ b und b ∣ a folgt a = b oder a = −b.

Die natürlichen Zahlen ℕ₀ bilden mit der Teilbarkeitsrelation eine quasigeordnete Menge und sogar einen vollständigen distributiven Verband. Die Verknüpfungen sind kleinstes gemeinsames Vielfaches (kgV) und größter gemeinsamer Teiler (ggT); 1 ist das kleinste, 0 das größte Element.

Regeln für Zweier-, Fünfer- und Zehnerpotenzen

Im Dezimalsystem genügt bei vielen Teilern die Untersuchung der letzten Ziffern:

Teilbarkeit durch 2 liegt genau dann vor, wenn die letzte Ziffer 0, 2, 4, 6 oder 8 ist. Durch 4 ist eine Zahl genau dann teilbar, wenn die letzten beiden Ziffern eine durch 4 teilbare Zahl bilden. Gleichwertig ist die Summe aus der letzten Ziffer und dem Doppelten der vorletzten Ziffer durch 4 teilbar.
Durch 8 ist eine Zahl genau dann teilbar, wenn die letzten drei Ziffern durch 8 teilbar sind. Gleichwertig ist die Summe aus letzter Ziffer, dem Doppelten der vorletzten und dem Vierfachen der vorvorletzten Ziffer durch 8 teilbar.
Allgemein ist eine Zahl genau dann durch 2ⁿ teilbar, wenn die aus den letzten n Ziffern gebildete Zahl durch 2ⁿ teilbar ist.
Durch 5 ist eine Zahl genau dann teilbar, wenn sie auf 0 oder 5 endet. Für 25 sind die Endungen 00, 25, 50 oder 75 möglich; für 125 die Endungen 000, 125, 250, 375, 500, 625, 750 oder 875. Allgemein prüft man für 5ⁿ die letzten n Ziffern.
Durch 10ⁿ ist eine Zahl genau dann teilbar, wenn ihre letzten n Ziffern 0 sind. Für 10, 100 und 1000 muss sie also auf 0, 00 beziehungsweise 000 enden.

Für Produkte aus Zweier- und Fünferpotenzen untersucht man die letzten max(m,n) Ziffern: Eine Zahl ist genau dann durch 2ᵐ5ⁿ teilbar, wenn diese Endzifferngruppe durch 2ᵐ5ⁿ teilbar ist. Beispiele: Für 20 muss die letzte Ziffer 0 und die vorletzte gerade sein; für 40 müssen die drittletzte und vorletzte Ziffer eine durch 4 teilbare Zahl bilden und die letzte Ziffer 0 sein; für 50 muss die Zahl auf 00 oder 50 enden.

Quersummen als allgemeines Verfahren

Eine n-Quersumme entsteht, indem man die Dezimaldarstellung von rechts in Blöcke aus n Ziffern teilt und diese Blöcke addiert. Bei der alternierenden n-Quersumme werden die Blockwerte abwechselnd addiert und subtrahiert. Bei der nichtalternierenden n-Quersumme werden sie nur addiert.

Der Grundgedanke lautet: Ist 10ⁿ − 1 ein Vielfaches des Teilers x, dann ist eine Zahl genau dann durch x teilbar, wenn ihre nichtalternierende n-Quersumme durch x teilbar ist. Ist 10ⁿ + 1 ein Vielfaches von x, gilt dieselbe Aussage für die alternierende n-Quersumme. Die Regeln folgen daraus, dass bei der Zerlegung der Zahl in n-stellige Blöcke die Differenzen beziehungsweise Summen der entsprechenden Zehnerpotenzen durch 10ⁿ − 1 beziehungsweise 10ⁿ + 1 teilbar sind.

Daraus ergeben sich unter anderem folgende Regeln:

Durch 3 oder 9: Die gewöhnliche Quersumme muss durch 3 beziehungsweise 9 teilbar sein.
Durch 11: Die nichtalternierende 2er-Quersumme oder alternativ die alternierende Quersumme muss durch 11 teilbar sein.
Durch 21: nichtalternierende 6er-Quersumme; durch 27: nichtalternierende 3er-Quersumme; durch 33: nichtalternierende 2er-Quersumme.
Durch 37: nichtalternierende 3er-Quersumme; durch 41: nichtalternierende 5er-Quersumme.
Durch 99: nichtalternierende 2er-Quersumme; durch 111, 333 und 999: nichtalternierende 3er-Quersumme.
Allgemein gilt die Regel für 9···9 = 10ⁿ − 1. Sie gilt ebenfalls für die Repunitzahl 1···1 = ∑ₖ₌₀ⁿ⁻¹ 10ᵏ.

Bei alternierenden Quersummen gelten beispielsweise: 7 und 13 verwenden die alternierende 3er-Quersumme, 17 die alternierende 8er-Quersumme, 19 die alternierende 9er-Quersumme, 23 die alternierende 11er-Quersumme, 73 die alternierende 4er-Quersumme, 77, 91, 143 und 1001 die alternierende 3er-Quersumme sowie 101 die alternierende 2er-Quersumme. Allgemein gilt die Regel für 100···001 = 10ⁿ + 1.

Die Quersumme muss nicht vollständig berechnet werden. Nach jeder Addition kann man den Rest modulo x weiterverwenden. Bei 7654 erhält man für die Teilbarkeit durch 3 die Restfolge 1, 1, 0, 1; der letzte Rest ist nicht 0, also ist 7654 nicht durch 3 teilbar.

Spezielle Regeln für 7, 17, 19 und 37

Für 7 gibt es mehrere äquivalente Verfahren. Trennt man die letzte Ziffer d₀ von D = 10R + d₀ ab, so gilt: D ist genau dann durch 7 teilbar, wenn D′ = R − 2d₀ durch 7 teilbar ist. Dies wiederholt man, bis eine kleine Zahl entsteht. Bei Bedarf kann man bei der Subtraktion 7, 14 oder 21 addieren und damit nur modulo 7 rechnen. Für 132797 ergibt die Folge 13279, 1323, 133, 14, 0; die Zahl ist daher durch 7 teilbar. Für 924214972 endet das Verfahren bei 6; die Zahl ist nicht durch 7 teilbar.

Eine weitere Regel teilt n = 100a + b in die letzten beiden Ziffern b und den Rest a. Dann ist n genau dann durch 7 teilbar, wenn 2a + b durch 7 teilbar ist. Für 3815 gilt 2 · 38 + 15 = 91, also ist 3815 durch 7 teilbar. Alternativ ist n = 10a + b genau dann durch 7 teilbar, wenn a − 2b durch 7 teilbar ist; aus 3815 wird 381 − 2 · 5 = 371 und anschließend 37 − 2 · 1 = 35 = 5 · 7. Bei einer Zerlegung vor den letzten drei Ziffern genügt es außerdem, die Differenz „letzte drei Ziffern minus übriger Teil“ zu prüfen, weil 1001 durch 7 teilbar ist.

Eine gewichtete Regel für 7 multipliziert die Ziffern von rechts mit 1, 3, 2, −1, −3, −2 und wiederholt dieses Muster. Ist die Summe durch 7 teilbar, gilt dies auch für die Ausgangszahl. Für 3815 ergibt sich 5 · 1 + 1 · 3 + 8 · 2 − 3 · 1 = 21.

Für 17 nutzt man 17 · 6 = 102: Bei n = 100a + b ist n modulo 17 gleich −2a + b. Man verdoppelt daher den linken Teil und zieht den rechten ab oder umgekehrt. Bei 5831 ergibt sich 2 · 58 − 31 = 85, also 5831 = 17 · 343.

Für 19 gilt bei n = 10a + b: n ist genau dann durch 19 teilbar, wenn a + 2b durch 19 teilbar ist. Aus 7904 wird 790 + 2 · 4 = 798 und danach 79 + 2 · 8 = 95 = 5 · 19.

Für 37 trennt man von rechts jeweils zwei Ziffern als Zahl ab und zieht das Elffache der nächsten Ziffer ab. Bei 19758 erhält man 58 − 7 · 11 + 19 = 0; daher ist die Zahl durch 37 teilbar.

Regeln für beliebige Teiler und Zahlensysteme

Für eine beliebige Primzahl p bestimmt man die Reste r₀, r₁, …, rₚ₋₂ der Zehnerpotenzen 10⁰, 10¹, …, 10ᵖ⁻² modulo p. Die Ziffern werden von rechts nach links mit diesen Gewichten multipliziert; nach p − 1 Ziffern wiederholt sich die Folge. Ist die gewichtete Summe durch p teilbar, ist auch die ursprüngliche Zahl Z durch p teilbar.

Die Begründung liefert der kleine fermatsche Satz 10ᵖ⁻¹ ≡ 1 (mod p). Deshalb haben Zehnerpotenzen, deren Exponenten bei Division durch p − 1 denselben Rest besitzen, denselben Rest modulo p. Die Differenzen zwischen den tatsächlichen Zehnerpotenzen und den verwendeten Resten sind somit durch p teilbar.

Für eine beliebige Zahl n verwendet man die Primfaktorzerlegung und prüft die Teilbarkeit durch die einzelnen Primzahlpotenzen. Beispielsweise ist eine Zahl genau dann durch 75 = 3 · 5² teilbar, wenn sie durch 25 und durch 3 teilbar ist: Die letzten beiden Ziffern müssen 00, 25, 50 oder 75 sein und die Quersumme muss durch 3 teilbar sein. Bei einem Produkt genügt die Teilbarkeit durch einen beliebigen Teilfaktor.

Die Regeln lassen sich auf ein Zahlensystem zur Basis B übertragen. Geeignet sind Teiler T, die sich in teilerfremde Faktoren zerlegen lassen, welche Teiler von Bⁿ, Bⁿ − 1 oder Bⁿ + 1 sind; n sollte möglichst klein sein, für Kopfrechnen sind höchstens 4 sinnvoll. Ist Bⁿ − 1 ein Vielfaches von x, verwendet man die nichtalternierende n-Quersumme; ist Bⁿ + 1 ein Vielfaches, die alternierende n-Quersumme.

Beispiele: Für 2ⁿ − 1 gruppiert man die Dualdarstellung rechts in n-Bit-Blöcke und summiert deren Werte zur Basis 2ⁿ. 91₁₀ = 001011011₂ = 133₈ ist durch 7₁₀ = 2³ − 1 teilbar, weil 1₈ + 3₈ + 3₈ = 7₁₀. Durch 27 ist eine Zahl genau dann teilbar, wenn die Summe ihrer dezimalen Dreierblöcke durch 27 teilbar ist. Außerdem ist eine Zahl genau dann durch n teilbar, wenn ihre Darstellung zur Basis n mit einer 0 endet.

Teilbarkeit in der Algebra und algorithmische Komplexität

In einem kommutativen Ring R heißt a ein Teiler von b, wenn es ein Ringelement n ∈ R mit a · n = b gibt. Äquivalent gilt a ∣ b genau dann, wenn das von a erzeugte Hauptideal (a) das Hauptideal (b) umfasst: (a) ⊇ (b). In ℤ ist (2) die Menge aller Vielfachen von 2 und (4) die Menge aller Vielfachen von 4; weil (2) ⊇ (4), teilt 2 die 4. Besonders ergiebig ist die Teilbarkeitstheorie in Integritätsringen, also nullteilerfreien kommutativen unitären Ringen.

In nicht-kommutativen Ringen muss man die Seite angeben. a heißt linker Teiler von b, wenn b = a · x für ein x ∈ R; b ist dann ein rechtes Vielfaches von a. Dies entspricht der Inklusion der Rechtsideale bR ⊆ aR. Entsprechend gibt es rechte und zweiseitige Teiler beziehungsweise Vielfache.

In Körpern und Schiefkörpern ist die Teilbarkeitstheorie trivial: Jedes Element ist durch jedes andere von 0 verschiedene Element teilbar, weil alle von 0 verschiedenen Elemente Einheiten sind. Als Beispiel nennt der Artikel die reellen Zahlen.

Auch rechnerisch ist ein Teilbarkeitstest effizient: Ein Test auf m ∣ n in ℕ benötigt geeignet programmiert O(ld n) Speicherplatz und O(ld n/m) Rechenzyklen, wobei ld der Logarithmus zur Basis 2 und O(·) das Landau-Symbol bezeichnet. Die Berechnung des Quotienten n/m besitzt dieselben angegebenen Größenordnungen; der Artikel ordnet den Test deshalb, etwa für die Faktorisierung von n, den schnellen Algorithmen zu.