Vorbemerkungen zur elementaren Zahlentheorie

Es bezeichne

    die Gesamtheit der natürlichen Zahlen
   
    den Ring der ganzen Zahlen.
    den Körper der rationalen Zahlen.

In und sind beliebige Additionen und Multiplikationen ausführbar, in noch zusätzlich Subtraktionen und in überdies Divisionen durch Elemente . Für ein bezeichne

den ,,Ring der Reste bei Division durch m``. Hier werden zwei Elemente und addiert und multipliziert, indem jeweils a und b addiert resp. multipliziert werden und jeweils die (kleinsten) Divisionsreste bei Division durch m als Bild bekommen, also etwa für m=5

Eine kleine Überlegung ergibt, daß genau dann sogar ein Körper ist, wenn m eine Primzahl ist. Primzahlen werden meist mit p benannt und es wird auch geschrieben

Über diese Körper mit p Elementen hinaus gibt es noch weitere endliche Körper , deren Elementzahl sich dann stets als eine Primzahlpotenz erweist, die meist als geschrieben wird.
Für die Begründung dieser und der Aussagen, die im Folgenden gebraucht werden, kann jedes Buch über Zahlentheorie genommen werden, also etwa Wolfart [Wo]. Zur Einstimmung ist aber besonders empfehlenswert F. Ischebeck: ,,Einladung zur Zahlentheorie`` [Is].

kann auch verstanden werden als Ring der Restklassen , also gewisser Teilmengen von mit den Rechenregeln, die darauf von wie eben beschrieben induziert werden. Dabei bedeutet dann für und

genau, daß a und b bei der Division durch m denselben Rest haben oder, äquivalent, daß m ein Teiler von (a-b) ist, also . Hier bezeichnet , daß m ein Teiler von n ist, also ein existiert mit n=ml. besagt, daß eben m kein Teiler von n ist. In der elementaren Zahlentheorie zentral ist die folgende Aussage, die auf Pierre de Fermat (1640) zurückgeht und auch der ,,kleine Fermatsche Satz`` genannt wird (s. [Wo] S.35).
Für alle und p prim gilt

Weiter wird noch gebraucht die Eulersche -Funktion (s.[Wo] S.19), die die Anzahl der primen Restklassen mit zählt. Es ist

also insbesondere, wenn p und q Primzahlen sind

In Verallgemeinerung des kleinen Fermatschen Satzes gilt noch (dies wird meist als Übungsaufgabe gestellt (s.[K1] S.93)):Es seien

und

Dann gilt für alle