Mathematik: Beweis zu Mersenne-Primzahlen

Wenn n eine natürliche Zahl ist, dann nennt man 2ⁿ - 1 eine Mersenne-Zahl. Hat 2ⁿ - 1 keine Teiler außer 1 und sich selbst, spricht man von einer Mersenne-Primzahl. Zum Glück muss man bei der Suche nach diesen speziellen Primzahlen nicht alle natürlichen Zahlen ausprobieren. Denn eine Mersenne-Zahl 2ⁿ - 1 kann nur dann eine Primzahl sein, wenn n selbst eine Primzahl ist.

Der Beweis dafür ist nicht allzu schwer. Wir schauen uns an, was geschieht, wenn der Exponent n keine Primzahl ist. Beginnen wir zunächst mit dem einfachen Fall, dass n in die Faktoren 2 und m zerlegt werden kann. Es gilt also n = 2*m, n ist also keine Primzahl und es gilt m>1. Wir zeigen nun, dass dann auch die Mersenne-Zahl von 2*m keine Primzahl ist. Diese lautet:

2^2*m - 1

Wir können sie auch in folgender Form schreiben:

(2^m)² - 1

Dieser Ausdruck lässt sich nach der binomischen Formel

(a+b)*(a-b) = a² - b²

in zwei Faktoren zerlegen:

(2^m)² - 1 = (2^m + 1)*(2^m - 1)

Weil m>1 ist, haben wir die Mersenne-Zahl von 2*m somit in zwei Faktoren >3 zerlegt, es kann sich also um keine Primzahl handeln.

Der allgemeine Beweis funktioniert ganz ähnlich. n soll keine Primzahl und deshalb als Produkt vom p und q darstellbar sein (n = p*q, p und q > 1). Die Mersenne-Zahl

2^p*q - 1

zerlegen wir in die beiden Faktoren:

(2^p - 1)* (2^p*(q-1) + 2^p*(q-2) + 2^p*(q-3) + ... + 2^p*2 + 2^p + 1)

Beide Faktoren sind wegen p, q>1 ebenfalls größer als 1. Damit haben wir bewiesen, dass eine Mersenne-Zahl 2ⁿ - 1 keine Primzahl sein kann, wenn n keine Primzahl ist. Wer Mersenne-Primzahlen sucht, muss als Exponenten n deshalb immer eine Primzahl nehmen.