Teilbarkeit durch Primzahlen
aus Wikipedia, der freien Enzyklopädie
Die Teilbarkeit einer Zahl z durch große Primzahlen kann man im Dezimalsystem folgendermaßen überprüfen:
Hierzu wird zunächst eine Testzahl t aus der Primzahl p ermittelt. Dafür bestimmt man einen Zahlstumpf s, der aus allen Ziffern von p mit Ausnahme der letzten besteht. Abhängig von der letzten Ziffer von p (die nur 1, 3, 7 oder 9 sein kann) ergibt sich t wie folgt:
- Wenn die letzte Ziffer eine 1 ist, gilt:
- t = p - s
- Wenn die letzte Ziffer eine 3 ist, gilt:
- t = 3 · s + 1
- Wenn die letzte Ziffer eine 7 ist, gilt:
- t = 7 · s + 5
- Wenn die letzte Ziffer eine 9 ist, gilt:
- t = s + 1
Sei zum Beispiel p = 19. Dann ist:
- s = 1, t = 2.
Ist p = 46519. Dann folgt:
- s = 4651, t = 4652.
Nun wird auch die Zahl z in ihren Anfang a und ihre Endziffer e zerlegt. Sie ist genau dann durch p teilbar, wenn ihre Endziffer multipliziert mit der Testzahl und dann addiert zu ihrem Anfang (t · e + a) durch p teilbar ist:
Diesen Schritt kann man solange wiederholen, bis die Teilbarkeit offensichtlich ist.
[Bearbeiten] Beispiel
- Ist die Zahl 1069937 durch 46519 teilbar?
- Aus t = 4652, a = 106993 und e = 7 folgt
- t · e + a = 4652 · 7 + 106993 = 139557.
- Aus t = 4652, a = 106993 und e = 7 folgt
- Es ist nun zu prüfen, ob 139557 durch 46519 teilbar ist.
- Aus t = 4652, a = 13955 und e = 7 folgt
- t · e + a = 4652 · 7 + 13955 = 46519.
- Aus t = 4652, a = 13955 und e = 7 folgt
Und da 46519 durch 46519 teilbar ist (46519/46519=1), ist die Ausgangszahl 1069937 auch durch 46519 teilbar.
Da jedes Zwischenergebnis ein Vielfaches vom zu prüfenden Teiler ist, muss man nicht alle Schritte durchgehen, sondern kann aufhören, sobald man die Teilbarkeit sieht.
