Mathematik: Zahlentheorie: Mersennesche und Fermatsche Primzahlen

Vorbemerkung

Lemma: Es gilt: $X^{n}-Y^{n}=(X-Y)(X^{n-1}+X^{n-2}Y+...+XY^{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.