Pseudoprimzahlen: Division und Restklassen

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Nuvola apps bookcase 1.svg Pseudoprimzahlen

Einleitung[Bearbeiten]

Bei den Pseudoprimzahlen ist häufig von der Kongruenz die Rede. In der Mathematik wird die Kongruenz durch das Zeichen repräsentiert. Im Grunde ist es gar nicht so schwer zu verstehen. Das folgende Kapitel soll das Verständniss vereinfachen oder ermöglichen.

Die Divison[Bearbeiten]

Bei der Division handelt es sich um eine Operation, die ermittelt, wie sich eine Zahl zerlegen läßt. Um ein praktisches Beispiel zu nehmen:

Eine Kekspackung enthält 12 Kekse. Wieviele Kekse bekommt jeder, wenn drei Personen anwesend sind. Die Lösung ist klar: Wenn drei Personen anwesend sind, fallen auf jede Person 4 Kekse, da ja ist.

Was aber, wenn die Division nicht in einer ganzzahligen Lösung aufgeht? Wenn man 12 durch 5 teilt bekommt man als Ergebnis 2,4. Das ist eine gebrochene Zahl. Man kann das Ganze aber auch anders angehen:

DIV und MOD[Bearbeiten]

Man kann sagen 5 paßt in 12 zweimal rein, und es bleibt ein Rest von 2. Bildlich kann man sich das so vorstellen, dass man je zwei Haufen a 5 Kekse bildet, und die zwei übrigen Kekse entfernt.

Die zwei Haufen Kekse bilden den DIV und die zwei übriggebliebenen Kekse dem MOD. Dazu noch ein Beispiel:

17 DIV 7 = 2
17 MOD 7 = 3

Hier wurde der Modulo als Rechenoperator verwendet. Man kann das Ganze noch etwas anders darstellen:

Wenn 3 der Rest aus der ganzzahligen Division von 17 dividiert durch 7 ist, dann gilt: (17 - 3) ist durch 7 teilbar. Als Kongruenz ausgedrückt .
Die 3 läßt sich ohne Probleme auf die andere Seite der Kongruenz bringen: .

Was ist jetzt so besonderes an der Kongruenz und dem Modulo?[Bearbeiten]

Was kann man damit jetzt anfangen? Naja, der Modulo ist sehr nützlich bei dem quadratischen Rest, oder auch bei dem Chinesischen Restsatz.

Der quadratische Rest[Bearbeiten]

Wenn man Quadratzahlen einer ganzzahligen Division unterzieht, und der Divisor ist dann noch eine Primzahl, so bekommt man interessante Muster. Teilen wir die Quadratzahlen testweise einmal durch die 7:

(naja, hier könnten wir schon aufhören)
(Schluß)

Mehr Quadratische Reste als 0, 1, 2 und 4 bekommen wir, bezüglich der Division durch 7 nicht. Was können wir aus diesen Resten schließen? Wir können schliessen, dass etwa die Zahlenfolge 7n+4 Quadratzahlen enthält: 4, 11, 18, 25, 32, 39, 46, 53, 60, 67, 74, 81, ... . Im Gegenzug können wir schließen, dass etwa die Zahlenfolge 7n+5 keine Quadratzahlen enthält: 5, 12, 19, 26, 33, 40, 47, 54, 61, 68, 75, 82 ... . Man braucht gar nicht alle Zahlen dieser Folge zu überprüfen. Die Folge ist frei von Quadratzahlen.