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:

$a^{p}\equiv a{\pmod {p}}$

wobei a eine ganze Zahl und p eine Primzahl sind (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

$a^{p-1}\equiv 1{\pmod {p}}$

bringen.

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 allen Zahlen aus A kongruent zum Produkt aller Zahlen aus B ist:

$1\cdot 2\cdot 3\cdot \dots \cdot (p-1)\equiv (1\cdot a)\cdot (2\cdot a)\cdot \dots \cdot ((p-1)\cdot a){\pmod {p}},$

also

$W\equiv W\cdot a^{p-1}{\pmod {p}},$

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

$a^{p-1}\equiv 1{\pmod {p}}$

Verallgemeinerung

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

$a^{\varphi (n)}\equiv 1{\pmod {n}}$

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

$2^{p}\equiv 2\mod p$ .

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

$2^{p}\equiv 2\mod p$ .

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:

$b^{p}\equiv b\mod p$

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:

$a^{(7-1)*c}\equiv 1\mod 7$ für alle $c\geq 1$

oder allgemein:

$a^{(p-1)*c}\equiv 1\mod p$ für alle $c\geq 1$ 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:

$a^{p-1}-1\equiv 0\mod p$

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:$1*17\mod 257=17\mod 257=17$

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

Schritt 2:$17*17\mod 257=289\mod 257=32$

Schritt 3:$32*17\mod 257=544\mod 257=30$

Schritt 4:$30*17\mod 257=510\mod 257=253$

Schritt 5:$253*17\mod 257=4301\mod 257=189$

Schritt 6:$189*17\mod 257=3213\mod 257=129$

Schritt 7:$129*17\mod 257=2193\mod 257=137$

Schritt 8:$137*17\mod 257=2329\mod 257=16$

Schritt 9:$16*17\mod 257=272\mod 257=15$

Schritt 10:$15*17\mod 257=255\mod 257=255$

Schritt 11:$255*17\mod 257=4335\mod 257=223$

Schritt 12:$223*17\mod 257=3791\mod 257=193$

Schritt 13:$193*17\mod 257=3281\mod 257=197$

Schritt 14:$197*17\mod 257=3349\mod 257=8$

Schritt 15:$8*17\mod 257=136\mod 257=136$

Schritt 16:$136*17\mod 257=2312\mod 257=256$ Diesen Schritt bitte merken!

Schritt 17:$256*17\mod 257=4352\mod 257=240$

Schritt 18:$240*17\mod 257=4080\mod 257=225$

Schritt 19:$225*17\mod 257=3825\mod 257=227$

Schritt 20:$227*17\mod 257=3859\mod 257=4$

Schritt 21:$4*17\mod 257=68\mod 257=68$

Schritt 22:$68*17\mod 257=1156\mod 257=128$

Schritt 23:$128*17\mod 257=2176\mod 257=120$

Schritt 24:$120*17\mod 257=2040\mod 257=241$

Schritt 25:$241*17\mod 257=4097\mod 257=242$

Schritt 26:$242*17\mod 257=4114\mod 257=2$

Schritt 27:$2*17\mod 257=34\mod 257=34$

Schritt 28:$34*17\mod 257=578\mod 257=64$

Schritt 29:$64*17\mod 257=1088\mod 257=60$

Schritt 30:$60*17\mod 257=1020\mod 257=249$

Schritt 31:$249*17\mod 257=4233\mod 257=121$

Schritt 32:$121*17\mod 257=2057\mod 257=1$ Nach 32 Schritten.

Da nach 32 Schritten die 1 wieder erreicht wurde, kann man sagen, das $17^{32}\mod 257=1$ gilt, und darraus folgern, das $17^{2*32}=17^{64},17^{4*32}=17^{128}$ und $17^{8*32}=17^{256}$ ebenfalls mod 257 = 1 ergeben. Woraus folgt, dass $18^{257-1}\equiv 1\mod 257$ ergibt. Dies hätte man auch schon aus Schritt 16 ersehen können, da 256 die Form (n-1) hat, und somit gilt $17^{16}\equiv -1\mod 257\Rightarrow 17^{2*16}\equiv (-1)*(-1)\mod 257=17^{32}\equiv 1\mod 257$.

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 $a^{n-1}\equiv 1\mod n=(a^{\frac {n-1}{2}}\mod n)*(a^{\frac {n-1}{2}}\mod n)\equiv 1\mod n=(a^{\frac {n-1}{2}})^{2}\equiv 1\mod n$

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

• Möglichkeit 1: $a^{\frac {n-1}{2}}\equiv 1\mod n$

und

• Möglichkeit 2: $a^{\frac {n-1}{2}}\equiv -1\mod n$ bzw.$a^{\frac {n-1}{2}}\equiv (n-1)\mod n$

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. $9^{2}\equiv 1\mod 10$
2. $9^{2}\equiv 1\mod 20$

Während für 1. noch gilt $9\equiv -1\mod 10$, gilt für 2. dieses nicht mehr.