Wie kommt man auf Idee? Mersenne Primzahl

10.10.2007, 10:24

quassel

Wie kommt man auf Idee? Mersenne Primzahl

Hallo.

Ich weiß nicht ob ich hier richtig bin, aber man kann mich ja hin und herschieben. Wir sollten in einem Vorkurs etwas beweisen, nämlich, das jede Mersenne-Primzahl,
$\begin{eqnarray*} M = 2^n - 1 \end{eqnarray*}$ , die Primzahl ist, dass dann auch gilt, das n eine Primzahl ist.

Wir haben das per Widerspruch gemacht, und wenn ich das bei der Aussagenlogik Sache richtig verstanden habe, ist es gleich zu zeigen, dass

$\begin{eqnarray*} a \Rightarrow b \end{eqnarray*}$ gleich ist,
wie nicht-b $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ nicht-a.

Wir sagen also, das angenommen n nicht Primzahl ist, dass dann eben M ebenfalls nicht Primzahl ist.

D.h. n nicht Primzahl, d.h. es gibt k,m $\begin{eqnarray*} \in \mathbb{N} \end{eqnarray*}$ so dass n = k*m, und dann hat der Typ irgendwas von geometrischer Reihe gesprochen und sowas aufgeschrieben:

$\begin{eqnarray*} 2^n - 1 = 2^{km} - 1 = (2^m -1) * \sum_{i=1}^{k}{2^{(k-i)m}} \end{eqnarray*}$

und damit hätte ich einen echten Teiler von 2^n-1 gefunden, also ist M nicht Primzahl. Aber wie komme ich denn auf so eine Idee? Ich mein das so mit der Summe zu machen.

Auch ist mir nicht ganz klar, ob das da wirklich gleich ist...

Ich hoff ich hab das da so einigermaßen richtig ausgedrückt.

Viele Grüße
quassel

10.10.2007, 10:46

therisen

Auf diesen Beitrag antworten »

RE: Wie kommt man auf Idee? Mersenne Primzahl

Zitat:

Original von quassel
Aber wie komme ich denn auf so eine Idee? Ich mein das so mit der Summe zu machen.

Nicht umsonst hat Mathematik sehr viel mit Kreativität zu tun. Du wirst dich im Laufe deines Studiums noch sehr oft fragen, wie man auf soetwas geniales gekommen ist. Der Trick, der hier verwendet wurde, gehört allerdings zu dem Standard-Repertoire eines (angehenden) Mathematikers und ist alles andere als genial Augenzwinkern

Es gilt nämlich ganz allgemein

$\begin{eqnarray*} a^n-b^n=(a-b)\sum_{k=0}^{n-1}a^{n-1-k}b^k \end{eqnarray*}$

Somit braucht man also nur das "richtige Auge", um die Aufgabe zu lösen.

Gruß, therisen

10.10.2007, 19:30

quassel

Auf diesen Beitrag antworten »

Hallo theriesen,

ja...ich glaube das merk ich schon gleich am Anfang. Ist fast ein wenig unheimlich, da trotz der logischen Fundierung, ich das immer noch so "vage" oder so, hmm naja so ungreifbar finde...Irgendwie ist die Mathematik doch relativ weit weg scheint es mir.

Aber das spornt mich auch irgendwie an smile

Ich nehme mal an $\begin{eqnarray*} a^n - b^n =(a - b) \sum_{k=0}^ {k-1}{a^{n-1-k}b^k} \end{eqnarray*}$ hat was mit dem binomischen Lehrsatz zu tun. Den haben wir nicht besprochen, deswegen war es mir nicht ganz klar, warum er von geometrischer Reihe da spricht.

Aber mit der Formel kann ich ja einfach b = 1 einsetzen und a = 2^m, und dann hab ich (ich hab i als Zählvariable anstatt k)
$\begin{eqnarray*} 2^n - 1 = (2^m - 1) \sum_{i=0}^ {k-1}{2^{m(n-1-i)}} \end{eqnarray*}$

Kann es sein, dass hier das mit der geometrischen Reihe evtl. funktioniert?
Dann bräuchte ich den binomischen Satz nicht...
Kann ich die summe auch von i=1 bis k laufen lassen?

Vielen dank für deine Hilfe,
einen schönen abend
quassel

10.10.2007, 19:43

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von quassel
$\begin{eqnarray*} 2^n - 1 = (2^m - 1) \sum_{i=0}^ {k-1}{2^{m(n-1-i)}} \end{eqnarray*}$

Das ist nicht ganz richtig ( $\begin{eqnarray*} a=2^m, b=1, n=k, k=i \end{eqnarray*}$ )

$\begin{eqnarray*} 2^n - 1 = (2^m - 1) \sum_{i=0}^ {k-1}{2^{m(k-1-i)}} \end{eqnarray*}$

Eine Indexverschiebung liefert

$\begin{eqnarray*} \sum_{i=0}^ {k-1}{2^{m(k-1-i)}}=\sum_{i=1}^ {k}{2^{m(k-1-(i-1))}}=\sum_{i=1}^ {k}{2^{m(k-i)}} \end{eqnarray*}$

Im Spezialfall b=1 ist das tatsächlich die geometrische Summenformel.

Gruß, therisen

Neue Frage »

Antworten »

Wie kommt man auf Idee? Mersenne Primzahl

Verwandte Themen