Mathematische Ü-Eier (Primzahlen 2 )

 

In der nächsten Tabelle berechnen wir Ausdrücke der Form

a^p mod p

 

p\a		0	1	2	3	4	5	6	7	8	9	10
2
3
4
5
6
7
8
9
10
11

 

Die Tabelle lässt Folgendes vermuten:

Vermutung 

Ist p eine Primzahl, so gilt für alle a =0,1,..., p -1

a^p mod p   =   a

der `kleine Satz von Fermat' 

Diese Vemutung ist in der Tat richtig. Sie wurde im 17. Jahrhundert von Pierre Fermat bewiesen.
Man spricht vom `kleinen Satz von Fermat'.

Nach Division durch a kann man auch schreiben

kleiner Fermat 

Ist p eine Primzahl, so gilt für alle a =0,1,..., p -1

a^p-1 mod p   =   1

 

Den kleinen Fermat kann man verallgemeinern zu:

ein Satz von Euler 

Ist a teilerfremd zu den beiden (verschiedenen) Primzahlen p und q , so gilt:

a^(p-1)·(q-1) mod p·q   =   1

Seite 9/17