Mathematik: Zahlentheorie: Mersennesche und Fermatsche Primzahlen

Vorbemerkung

Lemma: Es gilt: $X^n-Y^n=(X-Y)(X^{n-1}+X^{n-2}Y+...+X{Y}^{n-2}+Y^{n-1})$

Beweis: $(X-Y)\sum _{i=0}^{n-1}{X}^{n-1-i}{Y}^i=\sum _{i=0}^{n-1}{X}^{n-i}{Y}^i-\sum _{i=0}^{n-1}{X}^{n-1-i}{Y}^{i+1}=X^n+\sum _{i=1}^{n-1}{X}^{n-i}{Y}^i-\sum _{i=0}^{n-2}{X}^{n-(i+1)}{Y}^{i+1}-Y^n=X^n-Y^n$

Mersennesche Primzahlen

Wir fragen, welche Primzahlen der Form $2^n-1$ es gibt, wobei n eine natürliche Zahl ist.

Satz: Ist $2^n-1$ eine Primzahl, so ist auch $n$ eine Primzahl.

Beweis: Sei eine Darstellung $n=ab$ mit natürlichen Zahlen a,b gegeben. Wir setzen im Lemma $X=2^a$, $Y=1$ und $n=b$ ein und erhalten, dass $2^a-1|2^n-1$. Da $2^n-1$ als prim vorausgesetzt wurde, folgt $2^a-1=1$ oder $2^a-1=2^n-1$, also a=1 oder a=n.

Primzahlen der Form $2^p-1$ heißen Mersennesche Primzahlen.

Fermatsche Primzahlen

Wir fragen nun nach Primzahlen der Form $2^n+1$.

Satz: Ist $2^n+1$ eine Primzahl, so ist $n=2^k$ 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 $n=(2a+1)b$ mit natürlichen Zahlen a,b. Wir setzen im Lemma $X=2^b$, $Y=-1$ und $n=2a+1$ ein und erhalten, dass $2^b+1|2^n+1$. Da $2^n+1$ als prim vorausgesetzt wurde, folgt $2^b+1=1$ - was nicht möglich ist - oder $2^b+1=2^n+1$, also b=n und 2a+1=1.

Primzahlen der Form $2^{2^n}+1$ heißen Fermatsche Primzahlen.