Unteilbar Beweis zu Mersenne-Primzahlen

Jeder Computer mit Internetanschluss kann an der Jagd auf Mersenne-Primzahlen teilnehmen. Die besonderen Eigenschaften dieser Zahlen erleichtern die Suche - trotzdem dauert die Prüfung einer Zahl mehrere Tage.

Primzahlpionier Marin Mersenne (1588 - 1648)
imago/ Leemage

Primzahlpionier Marin Mersenne (1588 - 1648)


Wenn n eine natürliche Zahl ist, dann nennt man 2n - 1 eine Mersenne-Zahl. Hat 2n - 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 n ausprobieren. Denn eine Mersenne-Zahl 2n - 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:

22*m - 1

Wir können sie auch in folgender Form schreiben:

(2m)2 - 1

Dieser Ausdruck lässt sich nach der binomischen Formel

(a+b)*(a-b) = a2 - b2

in zwei Faktoren zerlegen:

(2m)2 - 1 = (2m + 1)*(2m - 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

2p*q - 1

zerlegen wir in die beiden Faktoren:

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

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

hda

Mehr zum Thema


© SPIEGEL ONLINE 2013
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.