Pseudoprimzahlen: Kongruenz und Restklassen

Pseudoprimzahlen

Einleitung

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

Die Divison

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 $3\cdot 4=12$ 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:

Division mit Rest (DIV und MOD)

Man kann sagen, 5 passt in 12 zweimal rein, und es bleibt ein Rest von 2. Bildlich kann man sich das so vorstellen, dass man je zwei Haufen à 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 'MOD' 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 $(17-3)\equiv 0{\pmod {7}}$.

Die 3 lässt sich ohne Probleme auf die andere Seite der Kongruenz bringen: $17\equiv 3{\pmod {7}}$.

Kongruenz

Kongruenz ist in der Zahlentheorie eine Beziehung zwischen ganzen Zahlen. Man nennt zwei ganze Zahlen $a$ und $b$ kongruent modulo $m$ (= eine weitere ganze Zahl), wenn sie bei der Division durch $m$ beide denselben Rest haben. Das ist genau dann der Fall, wenn ihre Differenz ein ganzzahliges Vielfaches von $m$ ist. Stimmen die Reste hingegen nicht überein, so nennt man die Zahlen inkongruent modulo $m$.

Schreibweise als Formel:

$a\equiv b{\pmod {m}}\quad$ $a$ und $b$ sind kongruent modulo $m$

$a\not \equiv b{\pmod {m}}\quad$ $a$ und $b$ sind inkongruent modulo $m$

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

Was kann man damit jetzt anfangen?

• Alle Primzahltests beruhen auf Kongruenzen.
• Der Modulo ist sehr nützlich beim quadratischen Rest.
• Der größte gemeinsame Teiler (ggT) kann durch Berechnung von Divisionsresten ermittelt werden.

Der quadratische Rest

Wenn man Quadratzahlen einer ganzzahligen Division mit Rest unterzieht, bekommt man interessante Muster. Teilen wir die Quadratzahlen testweise einmal durch 7:

$0\equiv 0{\pmod {7}}$

$1\equiv 1{\pmod {7}}$

$4\equiv 4{\pmod {7}}$

$9\equiv 2{\pmod {7}}$

$16\equiv 2{\pmod {7}}$ (naja, hier könnten wir schon aufhören)

$25\equiv 4{\pmod {7}}$

$36\equiv 1{\pmod {7}}$

$49\equiv 0{\pmod {7}}$ (Schluss)

Mehr quadratische Reste als 0, 1, 2 und 4 bekommen wir, bei der Division durch 7 nicht. Was können wir aus diesen Resten schließen? Wir können schließen, 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.