Exkurs: Teilbarkeit und Primzahlen¶
Lässt sich eine natürliche Zahl ohne Rest durch eine natürliche
Zahl
teilen, so nennt man
ein Vielfaches von
oder
einen Teiler von
. Bisweilen schreibt man anstelle von
„
ist Teiler von
“ auch in Kurzform
.
Jede Zahl hat die Zahl
als Teiler, denn es gilt stets
. Ein Teiler, der sowohl zu einer Zahl
als auch
zu einer Zahl
gehört, heißt gemeinsamer Teiler von
und
. Haben beide Zahlen keinen gemeinsamen Teiler außer der Zahl
, so nennt man die Zahlen teilerfremd.
Die Primfaktorenzerlegung
Hat eine natürliche Zahl nur zwei Teiler (
und die Zahl
selbst), so heißt sie Primzahl. Die ersten Primzahlen
sind:
Jede Zahl, die keine Primzahl ist, wird zerlegbar genannt, denn sie lässt sich ohne Rest in mehrere andere Zahlen aufteilen. Hierzu ist folgendes Vorgehen nützlich:
- Zunächst wird geprüft, ob die zu prüfende Zahl
durch eine beliebige, betraglich kleinere Primzahl
teilbar ist.
- Wird eine Primzahl
gefunden ist, die ein Teiler von
ist, so wird diese Primzahl notiert und
durch
geteilt.
- Mit dem Ergebnis der Division wird erneut mit dem 1. Schritt begonnen. Diese Wiederholung wird so lange fortgesetzt, bis keine weitere Aufteilung in Primzahlen möglich ist.
Das obige Verfahren wird auch als „Primfaktorzerlegung“ einer Zahl bezeichnet.
Beispiel:
Multipliziert man alle Primfaktoren einer Zahl miteinander, wobei einzelne Faktoren mehrfach auftreten dürfen, so erhält man als Ergebnis wiederum die ursprüngliche Zahl. Die gleiche Methode wird auch zur Ermittlung von Primzahlen mittels Computern eingesetzt.[1]
Weitere Teilbarkeitsregeln
, wenn die letzte Ziffer durch
teilbar ist.
, wenn die Quersumme der Zahl durch
teilbar ist.
, wenn die aus den beiden letzten Ziffern bestehende Zahl durch 4 teilbar ist.
, wenn die letzte Ziffer gleich
oder
ist.
, wenn die letzte Ziffer durch
und die Quersumme der Zahl durch
teilbar ist.
, wenn die aus den drei letzten Ziffern bestehende Zahl durch
teilbar ist.
, wenn die Quersumme der Zahl durch
teilbar ist.
, wenn ihre letzte Ziffer gleich
ist.
Die Quersumme bezeichnet dabei die Summe der Ziffern einer Zahl. Beispielsweise
ist die Quersumme der Zahl ; somit ist nach der
obigen Regel
durch
teilbar. Für die Zahl
existiert keine triviale Teilbarkeitsregel.
Anmerkungen:
[1] | Der als „Sieb des Eratosthenes“ bekannte Algorithmus prüft dabei gemäß der obigen Methode für beliebig große natürliche Zahlen, ob diese bereits eine der bereits bekannten Primzahlen als Faktor enthalten. Ist dies der Fall, so wird die Zahl (und ihre Vielfachen) als Nicht-Primzahl markiert und die Prüfung mit der nächsten Zahl fortgesetzt. Enthält eine Zahl keine kleinere Primzahl als Faktor, so stellt sie eine Primzahl dar und wird in die Liste der bekannten Primzahlen aufgenommen. |
[2] | Der Beweis hierfür ist beispielsweise in [Bittner1979] auf Seite 33 ff. aufgeführt. |