Kleiner fermatscher Satz

Der kleine fermatsche Satz, kurz der kleine Fermat, ist ein Lehrsatz in der Zahlentheorie. Er macht eine Aussage über die Eigenschaften von Primzahlen und wurde aufgestellt im 17. Jahrhundert von Pierre de Fermat. Dieser Satz beschreibt eine allgemein gültige Kongruenz:

wobei a eine ganze Zahl und p eine Primzahl ist (die weitere Symbolik wird im Artikel Kongruenz beschrieben). Falls a kein Vielfaches von p ist, kann man das Resultat in die häufig benutzte Form

bringen.

Inhaltsverzeichnis

1 Beweis 2 Verallgemeinerung 3 Praktische Anwendung auf Primzahlen 3.1 Eine kleine Fingerübung 3.2 Drei Tabellen 3.3 zu Euler

Beweis

Der Beweis beruht auf der Tatsache, dass, wenn zwei Zahlen a und b zueinander inkongruent (modulo einer festen Zahl n) sind, auch die beiden Produkte x·a und x·b inkongruent modulo n sind für x>0 und ggT(x, n)=1. Im folgenden betrachtet man zum einen die Menge A aller Reste (mod p) - also alle natürlichen Zahlen kleiner als p, und zum anderen die Menge B, die diese Reste multipliziert mit a enthält. Zwei beliebige Zahlen aus A sind zueinander inkongruent modulo p. Aus dem oberen Satz folgt, dass damit auch zwei beliebige Zahlen aus B zueinander inkongruent sind. Dadurch ergibt sich, dass das Produkt über alle Zahlen aus A kongruent zum Produkt aller Zahlen aus B ist:

also

wobei W das Produkt 1·2·3·...·(p-1) ist. Da es in Restklassenkörpern stets ein multiplikatives Inverses gibt, kann man diese W dividieren und man erhält:

Verallgemeinerung

Man kann den kleinen fermatschen Satz zum Satz von Euler verallgemeinern: Für zwei teilerfremde Zahlen n und a gilt:

wobei φ(n) die Eulersche Phi-Funktion bezeichnet. Diese hat als Ergebnis die Anzahl der Zahlen zwischen 1 und n-1 welche teilerfremd zu n sind. Ist n eine Primzahl, so ist φ(n) = n-1, so dass man Fermats kleinen Satz als Spezialfall erhält.

Mit Hilfe des kleinen fermatschen Satzes entwickelte Fermat den fermatschen Primzahltest.

Praktische Anwendung auf Primzahlen

Wenn eine natürliche Zahl p eine Primzahl ist, dann gilt

.

Hätte man diese Aussage umdrehen können, also sagen können, wenn für eine natürliche Zahl p gilt:

.

diese eine Primzahl ist, hätte man einen prima Primzahlengenerator bekommen können. Dem ist aber nicht so.

In Wirklichkeit gibt es auch Nichtprimzahlen, auf die diese Eigenschaft zutrifft: Die Pseudoprimzahlen.

Man kann aber den Satz auf alle Basen 1 < b < p erweitern. Wenn man also sagen kann, das bei einem natürlichen p für alle Basen b mit 1 < b < p gilt:

dann muß diese Zahl p eine Primzahl sein.

Dazu muß man nicht alle Basen 1 < b < p durchtesten, sondern es reicht, das man alle Primzahlen r 1 < r < p benutzt.

Der Nachteil an diesem Verfahren ist, das es sehr langsam und aufwändig ist (das Testen auf Primzahlen über die Teilbarkeit ist schneller).

Wie funktioniert der Fermatsche Satz? Wenn man eine Zahl immer wieder mit sich multipliziert, dann bekommt man gewisse Zyklen bezüglich der Modulo-Operation:

Beispiel: 7

	2	2 mod 7	3	3 mod 7	5	5 mod 7
0	1	1	1	1	1	1
1	2	2	3	3	5	5
2	4	4	9	2	25	4
3	8	1	6	6	20	6
4	2	2	18	4	30	2
5	4	4	12	5	10	3
6	8	1	15	1	15	1
7	2	2	3	3	5	5

und so weiter. In Bezug auf die 7 ergibt sich bei der 2 folgender Zyklus: .. 1, 2, 4, 1, 2, 4, .. . Bei der 3: .. 1, 3 ,2 ,6, 4, 5, 1, 3, .. .

Für alle drei Basen 2, 3 und 5 gilt zur Zahl 7 folgende Regel:

für alle

oder allgemein:

für alle und alle natürlichen a für die gilt 1 < a < p

Im Beispiel des 2er-Zyklus .. 1, 2, 4, 1, 2, 4, .. zeigt sich, dass man den Algorithmus verkürzen kann, wenn sich zeigen läßt, dass der Zyklus kürzer .. 1, 2, 4, .. ist, als benötigt.

Außerdem hat es sich als sinnvoll gezeigt, dass man folgende Formel benutzt:

Eine kleine Fingerübung

Man nehme eine ungerade Zahl n und eine natürliche Zahl a die kleiner als n, aber größer gleich 2 ist.

Beispiel: n=257 und a=17

Als Startzahl i wählen wir die 1. Nun wird folgendes getan:

Schritt 1:

Das war ein Schritt, und das Ergebnis 17 ist das neue 'i'. Dieser Vorgang wird solange wiederholt, bis 'i' wieder 1 ist:

Schritt 2:

Schritt 3:

Schritt 4:

Schritt 5:

Schritt 6:

Schritt 7:

Schritt 8:

Schritt 9:

Schritt 10:

Schritt 11:

Schritt 12:

Schritt 13:

Schritt 14:

Schritt 15:

Schritt 16: Diesen Schritt bitte merken!

Schritt 17:

Schritt 18:

Schritt 19:

Schritt 20:

Schritt 21:

Schritt 22:

Schritt 23:

Schritt 24:

Schritt 25:

Schritt 26:

Schritt 27:

Schritt 28:

Schritt 29:

Schritt 30:

Schritt 31:

Schritt 32: Nach 32 Schritten.

Da nach 32 Schritten die 1 wieder erreicht wurde, kann man sagen, das gilt, und daraus folgern, das und ebenfalls mod 257 = 1 ergeben. Woraus folgt, dass ergibt. Dies hätte man auch schon aus Schritt 16 ersehen können, da 256 die Form (n-1) hat, und somit gilt .

Nebenbei, so schön, wie an den Schritten 2, 8, 14, 20, 26 und 32 kann man nicht immer verfolgen, durch eine Halbierung alle 6 Schritte, das nach einem berechenbaren Schritt die 1 erreichbar ist.

Drei Tabellen

Primzahl 17
	1	2	4	8	16	32
2	2	4	[16]	1	1	1
3	3	9	13	[16]	1	1
5	5	8	13	[16]	1	1
7	7	15	4	[16]	1	1
11	11	2	4	[16]	1	1
13	13	[16]	1	1	1	1

zu Euler

Es gilt

Dabei gibt es, für eine Primzahl n und die Basis a zwei Möglichkeiten:

• Möglichkeit 1:

und

• Möglichkeit 2: bzw.

da 1 = 1*1 bzw. 1 = (-1)*(-1) gilt. Es gibt, auf die Modulo-Operation bezogen, noch die dritte Möglichkeit: 1 = x * x:

1. 
2. 

Während für 1. noch gilt , gilt für 2. dieses nicht mehr.

Help build the largest human-edited directory on the web.

Submit a Site - Open Directory Project - Become an Editor