Teilbarkeit ist eine mathematische Beziehung zwischen zwei ganzen Zahlen. Eine ganze Zahl ist durch eine andere ganze Zahl teilbar, wenn bei der Division kein Rest verbleibt, also die „Geteilt-Rechnung aufgeht“. So ist beispielsweise die Zahl 8 durch 4 teilbar, da 8 : 4 genau 2 ergibt; somit ist 4, aber auch 2, Teiler von 8. Dagegen ist die Zahl 9 nicht durch 4 teilbar, weil die 4 zweimal in die 9 „geht“, aber ein Rest von 1 übrig bleibt.
Die Zahl 11 hat nur zwei Teiler: 1 und die Zahl 11 selbst. Solche Zahlen nennt man Primzahlen. Die Zahl 12 dagegen hat viele Teiler: 1, 2, 3, 4, 6 und 12. Solche Zahlen nennt man hochzusammengesetzte Zahlen.
Die Funktion, die einer natürlichen Zahl n{\displaystyle n}
Eine ganze Zahl a{\displaystyle a}
und nennt ∣{\displaystyle \mid }
Insbesondere für Primzahlpotenzen gibt es die Sprechweise: pn{\displaystyle p^{n}}
wenn pn{\displaystyle p^{n}} die größte Potenz der Primzahl p{\displaystyle p}
Da 0⋅n=0{\displaystyle 0\cdot n=0}
Schreibt man denselben Sachverhalt in der Form a⋅0=0{\displaystyle a\cdot 0=0}
Die 1{\displaystyle 1}
Es gelte a∣b{\displaystyle a\mid b} und b≠0{\displaystyle b\neq 0}
Die Menge aller Teiler einer natürlichen Zahl n{\displaystyle n} nennt man die „Teilermenge von n{\displaystyle n}“. Die Quasiordnung der Teilbarkeit induziert auf ihr die Struktur eines Verbandes, man spricht deshalb auch vom „Teilerverband von n{\displaystyle n}“.
Die Menge aller Vielfachen einer natürlichen Zahl n{\displaystyle n} heißt entsprechend Vielfachenmenge. Bei den ganzen Zahlen Z{\displaystyle \mathbb {Z} } ist die Mächtigkeit dieser Menge abzählbar unendlich.
- Jede Zahl besitzt mindestens ihre trivialen Teiler, insbesondere sind die Einheiten ±1{\displaystyle \pm 1} Teiler einer jeden ganzen Zahl.
- Jede ganze Zahl ist ein (trivialer) Teiler der 0{\displaystyle 0}.
- Jede ganze Zahl teilt sich selbst (Reflexivität der Quasiordnung).
- Der kleinste positive Teiler ≠1{\displaystyle \neq 1}einer ganzen Zahl ist ein Primteiler.
Seien a{\displaystyle a}, b{\displaystyle b}, c{\displaystyle c}
- Gilt a∣b{\displaystyle a\mid b}, so gilt auch −a∣b{\displaystyle -a\mid b}und a∣−b{\displaystyle a\mid -b}. Man kann sich also bei der Untersuchung des Teilbarkeitsbegriffs auf natürliche Zahlen beschränken.
- Gilt a∣b{\displaystyle a\mid b} und b∣c{\displaystyle b\mid c}, so folgt a∣c{\displaystyle a\mid c}(Transitivität der Quasiordnung).
- Für k∈Z∖{0}{\displaystyle k\in \mathbb {Z} \setminus \{0\}}gilt: a∣b⇔ka∣kb{\displaystyle a\mid b\Leftrightarrow ka\mid kb}.
- Gilt a∣b{\displaystyle a\mid b} und c∣d{\displaystyle c\mid d}, so gilt auch ac∣bd{\displaystyle ac\mid bd}.
- Gilt a∣b{\displaystyle a\mid b} und a∣c{\displaystyle a\mid c}, so gilt auch a∣kb+lc{\displaystyle a\mid kb+lc}für alle ganzen Zahlen k{\displaystyle k}und l{\displaystyle l}.
- Gilt a∣b{\displaystyle a\mid b} und b∣a{\displaystyle b\mid a}so ist a=b{\displaystyle a=b}oder a=−b{\displaystyle a=-b}.
Die natürlichen Zahlen N0{\displaystyle \mathbb {N} _{0}}
- Eine Zahl ist genau dann durch 2 teilbar, wenn ihre letzte Ziffer gerade ist (0, 2, 4, 6 oder 8).
- Eine Zahl ist genau dann durch 4 teilbar, wenn die Zahl, die aus ihren letzten beiden Ziffern gebildet wird, durch 4 teilbar ist.
- Eine Zahl ist genau dann durch 8 teilbar, wenn die Zahl, die aus ihren letzten drei Ziffern gebildet wird, durch 8 teilbar ist.
- Allgemein ist eine Zahl genau dann durch 2n{\displaystyle 2^{n}}teilbar, wenn die Zahl, die aus ihren letzten n{\displaystyle n} Ziffern gebildet wird, durch 2n{\displaystyle 2^{n}} teilbar ist.
- Eine Zahl ist genau dann durch 5 teilbar, wenn ihre letzte Ziffer durch 5 teilbar ist (0 oder 5).
- Eine Zahl ist genau dann durch 25 teilbar, wenn die Zahl, die aus ihren letzten beiden Ziffern gebildet wird, durch 25 teilbar ist (00, 25, 50 oder 75).
- Eine Zahl ist genau dann durch 125 teilbar, wenn die Zahl, die aus ihren letzten drei Ziffern gebildet wird, durch 125 teilbar ist.
- Allgemein ist eine Zahl genau dann durch 5n{\displaystyle 5^{n}}teilbar, wenn die Zahl, die aus ihren letzten n{\displaystyle n} Ziffern gebildet wird, durch 5n{\displaystyle 5^{n}} teilbar ist.
- Eine Zahl ist genau dann durch 10 teilbar, wenn ihre letzte Ziffer eine 0 ist.
- Eine Zahl ist genau dann durch 100 teilbar, wenn die Zahl mit 00 endet.
- Eine Zahl ist genau dann durch 1000 teilbar, wenn die Zahl mit 000 endet.
- Allgemein ist eine Zahl genau dann durch 10n{\displaystyle 10^{n}}teilbar, wenn ihre letzten n{\displaystyle n} Ziffern jeweils 0 sind.
- Eine Zahl ist genau dann durch 20 teilbar, wenn ihre vorletzte Ziffer gerade ist (0, 2, 4, 6 oder 8) und ihre letzte Ziffer 0 ist.
- Eine Zahl ist genau dann durch 40 teilbar, wenn die Zahl, die aus der drittletzten und vorletzten Ziffer gebildet wird, durch 4 teilbar ist und die letzte Ziffer eine 0 ist.
- Eine Zahl ist genau dann durch 50 teilbar, wenn die Zahl auf 00 oder 50 endet.
- Allgemein ist eine Zahl genau dann durch 2m5n{\displaystyle 2^{m}5^{n}}teilbar, wenn die Zahl, die aus ihren letzten max(m,n){\displaystyle \max(m,n)}Ziffern gebildet wird, durch 2m5n{\displaystyle 2^{m}5^{n}} teilbar ist.
Will man für eine Zahl x{\displaystyle x}
Entsprechende Faktoren existieren für alle Zahlen, die mit 10 teilerfremd sind. Allerdings ist die Prüfung zum Teil schon für relativ kleine Zahlen unpraktisch (siehe zum Beispiel die unten angegebenen Regeln für Teilbarkeit durch 17 und 19).
Teilbarkeitsregeln basierend auf nichtalternierenden Quersummen[Bearbeiten | Quelltext bearbeiten]
Ist 10n−1{\displaystyle 10^{n}-1} ein Vielfaches der betrachteten Zahl x{\displaystyle x}, dann gilt die Teilbarkeitsregel: „Eine Zahl ist genau dann durch x{\displaystyle x} teilbar, wenn ihre nichtalternierende n{\displaystyle n}-Quersumme durch x{\displaystyle x} teilbar ist.“
Beispielsweise ist 9=101−1{\displaystyle 9=10^{1}-1}
- Eine Zahl ist genau dann durch 3 teilbar, wenn ihre Quersumme durch 3 teilbar ist.
- Eine Zahl ist genau dann durch 6 teilbar, wenn sie durch 2 und durch 3 teilbar ist.
- Eine Zahl ist genau dann durch 9 teilbar, wenn ihre Quersumme durch 9 teilbar ist.
- Eine Zahl ist genau dann durch 11 teilbar, wenn ihre nichtalternierende 2er-Quersumme durch 11 teilbar ist. Es gibt auch eine Teilbarkeitsregel mit der alternierenden Quersumme (siehe unten).
- Eine Zahl ist genau dann durch 21 teilbar, wenn ihre nichtalternierende 6er-Quersumme durch 21 teilbar ist.
- Eine Zahl ist genau dann durch 27 teilbar, wenn ihre nichtalternierende 3er-Quersumme durch 27 teilbar ist.
- Eine Zahl ist genau dann durch 33 teilbar, wenn ihre nichtalternierende 2er-Quersumme durch 33 teilbar ist.
- Eine Zahl ist genau dann durch 37 teilbar, wenn ihre nichtalternierende 3er-Quersumme durch 37 teilbar ist.
- Eine Zahl ist genau dann durch 41 teilbar, wenn ihre nichtalternierende 5er-Quersumme durch 41 teilbar ist.
- Eine Zahl ist genau dann durch 99 teilbar, wenn ihre nichtalternierende 2er-Quersumme durch 99 teilbar ist.
- Eine Zahl ist genau dann durch 111 teilbar, wenn ihre nichtalternierende 3er-Quersumme durch 111 teilbar ist.
- Eine Zahl ist genau dann durch 333 teilbar, wenn ihre nichtalternierende 3er-Quersumme durch 333 teilbar ist.
- Eine Zahl ist genau dann durch 999 teilbar, wenn ihre nichtalternierende 3er-Quersumme durch 999 teilbar ist.
- Allgemein ist eine Zahl genau dann durch 9…9=10n−1{\displaystyle 9\dotso 9=10^{n}-1}teilbar, wenn ihre nichtalternierende n{\displaystyle n}-Quersumme durch 10n−1{\displaystyle 10^{n}-1} teilbar ist.
- Allgemein ist eine Zahl genau dann durch 1…1=∑k=0n−110k{\displaystyle \textstyle 1\dotso 1=\sum _{k=0}^{n-1}10^{k}}(Repunitzahl) teilbar, wenn ihre nichtalternierende n{\displaystyle n}-Quersumme durch 1…1{\displaystyle 1\dotso 1}teilbar ist.
Die Quersumme muss nicht vollständig berechnet werden, sondern es genügt, den Rest einer Ziffer (oder Zifferngruppe) bei Division durch x{\displaystyle x} zu berücksichtigen. Es kann auch nach jeder Addition der Rest bei Division durch x{\displaystyle x} berechnet werden. Um z. B. zu ermitteln, ob 7654 durch 3 teilbar ist, kann man rechnen:
- Ziffer 7: Rest bei Division durch 3 ist 1: Summe 1 (Quersumme 7=2⋅3+1{\displaystyle 7=2\cdot 3+1})
- Ziffer 6: Rest bei Division durch 3 ist 0: Summe 1 ändert sich nicht (Quersumme 13=4⋅3+1{\displaystyle 13=4\cdot 3+1})
- Ziffer 5: diesmal ohne Bestimmung des Rests: Summe 1+5=6, Rest bei Division durch 3 ist 0 (Quersumme 18=6⋅3+0{\displaystyle 18=6\cdot 3+0})
- Ziffer 4: Summe 0+4=4, Rest bei Division durch 3 ist 1 (Quersumme 22=7⋅3+1{\displaystyle 22=7\cdot 3+1})
Da der im letzten Schritt berechnete Rest nicht Null ist, ist 7654 nicht durch 3 teilbar.
Teilbarkeitsregeln basierend auf alternierenden Quersummen[Bearbeiten | Quelltext bearbeiten]
Ist hingegen 10n+1{\displaystyle 10^{n}+1} ein Vielfaches der betrachteten Zahl x{\displaystyle x}, dann gilt die Teilbarkeitsregel: „Eine Zahl ist genau dann durch x{\displaystyle x} teilbar, wenn ihre alternierende n{\displaystyle n}-Quersumme durch x{\displaystyle x} teilbar ist.“
Betrachtet man beispielsweise die Zahl 7, so kann man durch Ausprobieren sehen, dass 7⋅143=1001=103+1{\displaystyle 7\cdot 143=1001=10^{3}+1}
- Eine Zahl ist genau dann durch 7 teilbar, wenn ihre alternierende 3er-Quersumme durch 7 teilbar ist.
- Eine Zahl ist genau dann durch 11 teilbar, wenn ihre alternierende Quersumme durch 11 teilbar ist. Es gibt auch eine Teilbarkeitsregel mit der nichtalternierenden 2er-Quersumme (siehe oben).
- Eine Zahl ist genau dann durch 13 teilbar, wenn ihre alternierende 3er-Quersumme durch 13 teilbar ist.
- Eine Zahl ist genau dann durch 17 teilbar, wenn ihre alternierende 8er-Quersumme durch 17 teilbar ist.
- Eine Zahl ist genau dann durch 19 teilbar, wenn ihre alternierende 9er-Quersumme durch 19 teilbar ist.
- Eine Zahl ist genau dann durch 23 teilbar, wenn ihre alternierende 11er-Quersumme durch 23 teilbar ist.
- Eine Zahl ist genau dann durch 73 teilbar, wenn ihre alternierende 4er-Quersumme durch 73 teilbar ist.
- Eine Zahl ist genau dann durch 77 teilbar, wenn ihre alternierende 3er-Quersumme durch 77 teilbar ist.
- Eine Zahl ist genau dann durch 91 teilbar, wenn ihre alternierende 3er-Quersumme durch 91 teilbar ist.
- Eine Zahl ist genau dann durch 101 teilbar, wenn ihre alternierende 2er-Quersumme durch 101 teilbar ist.
- Eine Zahl ist genau dann durch 137 teilbar, wenn ihre alternierende 4er-Quersumme durch 137 teilbar ist.
- Eine Zahl ist genau dann durch 143 teilbar, wenn ihre alternierende 3er-Quersumme durch 143 teilbar ist.
- Eine Zahl ist genau dann durch 1001 teilbar, wenn ihre alternierende 3er-Quersumme durch 1001 teilbar ist.
- Allgemein ist eine Zahl genau dann durch 100…001=10n+1{\displaystyle 100\dotso 001=10^{n}+1}teilbar, wenn ihre alternierende n{\displaystyle n}-Quersumme durch 10n+1{\displaystyle 10^{n}+1} teilbar ist.
Neben der schon genannten Teilbarkeitsregel mittels der alternierenden 3er-Quersumme gibt es für die 7 weitere, teils einfachere, Teilbarkeitsregeln. Diese ergeben sich aus der Betrachtung von Vielfachen der Zahl, die nah an 10er-Potenzen liegen, also beispielsweise im nächsten Beispiel 14⋅7=98{\displaystyle 14\cdot 7=98}
Da 98 und damit auch 98⋅a{\displaystyle 98\cdot a}
Für eine weitere Teilbarkeitsregel spaltet man eine Zahl in ihre letzte Ziffer b{\displaystyle b} und den Rest a{\displaystyle a} auf. Zum Beispiel 3815 in die Zahlen a=381{\displaystyle a=381}
Für 3815 muss man also überprüfen, ob 381−2⋅5=371{\displaystyle 381-2\cdot 5=371}
Man kann eine Zahl n{\displaystyle n} auch vor der drittletzten Ziffer spalten, so dass die letzten drei Ziffern die Zahl a{\displaystyle a} und die Ziffern davor die Zahl b{\displaystyle b} bilden. Dann zieht man b{\displaystyle b} von a{\displaystyle a} ab und prüft, ob diese Differenz durch 7 teilbar ist. Da
n=1000⋅b+a=1001⋅b+(a−b){\displaystyle n=1000\cdot b+a=1001\cdot b+(a-b)}und 1001⋅b{\displaystyle 1001\cdot b}
Ein Verfahren, um die Teilbarkeit durch 17 festzustellen, beruht auf der Identität 17 · 6 = 102. Deswegen gilt
100⋅a+b=102⋅a−2⋅a+b≡−2⋅a+bmod17{\displaystyle 100\cdot a+b=102\cdot a-2\cdot a+b\equiv -2\cdot a+b\mod 17}Man spaltet also die zu prüfende Zahl n{\displaystyle n} vor der vorletzten Stelle in zwei Teile, nimmt das Doppelte des linken Teils und zieht den rechten Teil ab (oder umgekehrt). Ist das Resultat durch 17{\displaystyle 17}
Beispiel: 5831=17⋅343{\displaystyle 5831=17\cdot 343}
Um die Teilbarkeit durch 19 zu überprüfen, spaltet man eine Zahl in ihre letzte Ziffer b{\displaystyle b} und den Rest a{\displaystyle a} auf. Zum Beispiel 7904 in die Zahlen a=790{\displaystyle a=790}
Für 7904 muss man also überprüfen, ob 798=790+2⋅4{\displaystyle 798=790+2\cdot 4}
Um die Teilbarkeit durch eine beliebige Zahl n{\displaystyle n} zu überprüfen, verwendet man deren Primfaktorzerlegung. Man überprüft dann die Teilbarkeit durch die einzelnen Primzahlpotenzen dieser Zerlegung.
Beispielsweise ist eine Zahl genau dann durch 75=3⋅52{\displaystyle 75=3\cdot 5^{2}}
Vergleiche auch Teilbarkeit für alle zu 10 teilerfremden Divisoren.
In einem Zahlensystem zur Basis B{\displaystyle B}
Die folgenden Teilbarkeitsregeln benutzen andere Stellenwertsysteme:
- Eine Zahl ist durch eine Zahl der Form 2n−1{\displaystyle 2^{n}-1}teilbar genau dann, wenn bei der Darstellung zur Basis 2n{\displaystyle 2^{n}} die Quersumme durch 2n−1{\displaystyle 2^{n}-1} teilbar ist. Die Darstellung zur Basis 2n{\displaystyle 2^{n}} ergibt sich leicht aus der Darstellung der Zahl im Dualsystem. Dazu wird die Zahl rechts beginnend in Gruppen von n{\displaystyle n} Stellen eingeteilt, der Dezimalwert der einzelnen Gruppen entspricht nun den Werten der Ziffern in der Darstellung zur Basis 2n{\displaystyle 2^{n}}. Zum Beispiel ist 9110{\displaystyle 91_{10}}durch 710=23−1{\displaystyle 7_{10}=2^{3}-1}teilbar, weil 9110=0010110112=1338{\displaystyle 91_{10}=001011011_{2}=133_{8}}im Oktalsystem (Basis 23{\displaystyle 2^{3}}) die Quersumme 18+38+38=710{\displaystyle 1_{8}+3_{8}+3_{8}=7_{10}}hat.
- Eine Zahl ist durch 27 teilbar genau dann, wenn ihre Quersumme zur Basis 1000 durch 27 teilbar ist. Diese Quersumme kann man erhalten, indem man ihre dezimale Darstellung rechts beginnend in Dreierblöcke einteilt und die Summe dieser Blöcke bildet.
- Eine Zahl ist durch n{\displaystyle n} teilbar genau dann, wenn ihre Darstellung als n{\displaystyle n}-basische Zahl mit einer 0 endet.
Weitere Teilbarkeitseigenschaften findet man im Artikel Kongruenz (Zahlentheorie).
Der Teilbarkeitsbegriff wird auch wesentlich allgemeiner in kommutativen Ringen betrachtet. Die Definition von Teilbarkeit in natürlichen und ganzen Zahlen wird hier direkt übernommen:
Es sei R{\displaystyle R}
In Ringen teilt a{\displaystyle a} genau dann b{\displaystyle b}, wenn das von a{\displaystyle a} erzeugte Hauptideal (a){\displaystyle (a)}
Ein einfaches Beispiel aus den ganzen Zahlen: Das von 2{\displaystyle 2}
Die fruchtbarsten Teilbarkeitseigenschaften erhält man in Integritätsringen, das sind nullteilerfreie kommutative unitäre Ringe.