Lemma: Es gilt:
Beweis:
Wir fragen, welche Primzahlen der Form
es gibt, wobei n eine natürliche Zahl ist.
Satz: Ist
eine Primzahl, so ist auch
eine Primzahl.
Beweis: Sei eine Darstellung
mit natürlichen Zahlen a,b gegeben. Wir setzen im Lemma
,
und
ein und erhalten, dass
. Da
als prim vorausgesetzt wurde, folgt
oder
, also a=1 oder a=n.
Primzahlen der Form
heißen Mersennesche Primzahlen.
Wir fragen nun nach Primzahlen der Form
.
Satz: Ist
eine Primzahl, so ist
für eine nicht-negative ganze Zahl k.
Beweis:
Wir zeigen, dass n keinen ungeraden Teiler größer als 1 hat. Daraus folgt dann, dass n keinen ungeraden Primfaktor enthält, also eine Potenz von 2 ist.
Angenommen wir haben
mit natürlichen Zahlen a,b. Wir setzen im Lemma
,
und
ein und erhalten, dass
. Da
als prim vorausgesetzt wurde, folgt
- was nicht möglich ist - oder
, also b=n und 2a+1=1.
Primzahlen der Form
heißen Fermatsche Primzahlen.