Primzahlen Beweis?

Ich soll folgendes beweisen : eine Zahl n aus der natürlichen Zahlen ist eine Primzahl, wenn 2^n -1 eine Primzahl ist . Mein Ansatz: kontra Position bilden ist = eine Zahl n ist keine Primzahl, wenn 2^n -1 keine Primzahl ist.

wenn n keine Primzahl, kann ich sie ja wie folgt schreiben n=a*b (a,b>1).

dann habe ich folgendes: 2^(a*b)-1 das wiederum ist =(2^a-1)(2^a(b-1)+2^a(b-2)…..,+2^a+1) den Teil hatte ich aus der Aufgabe davor, den ich zeigen musste.

Und jetzt weiß ich weiter. Ich muss doch irgendwie zeigen, dass 2^n -1 keinen Teil außer sich selbst um die eins hat.

Answer 1

[FataMorgana2010]

Falsch herum gelesen.

Was du dazu wissen musst:

$\frac{x^n-1}{x-1} = x^{n-1} + x^{n-2} + ... + 1$ d. h. für ganzzahliges x ist x^n-1 immer durch x-1 ohne Rest teilbar (das ist die Formel für die geometrische Reihe).

Angenommen, p ist keine Primzahl, dann kannst du das als Produkt zweier Zahlen a und b schreiben (wobei weder a noch b 1 sind). Und dann gilt mit der obigen Formel

$\frac{2^{ab}-1}{2^a-1} = \frac{(2^a)^b-1}{2^a-1} = (2^a)^{b-1} + (2^a)^{b-2} + ... + 1$

Also ist 2^ab-1 durch 2^a-1 und mit der gleichen Argumentation auch durch 2^b-1 teilbar.

Comments

[Todaboi]

Wie meinst du?

[FataMorgana2010]

@Todaboi

Ich hatte das falsch herum gelesen. Jetzt ist es richtig.

[Todaboi]

@FataMorgana2010

Verstehe ich das richtig du hast gezeigt dass p keine Primzahl ist . Somit gilt die Kontraposition. Somit müsste die kontraposition der Kontraposition also unsere aussage von Anfang gelten?

[FataMorgana2010]

@Todaboi

Unsere Aussage ist:

Wenn 2^p - 1 eine Primzahl ist, dann ist p eine Primzahl.

Kontraposition:

Wenn p keine Primzahl ist, dann ist 2^p - 1 keine Primzahl.

Ich nehme an, p ist keine Primzahl:

--- Beweis von oben: 2^p - 1 ist keine Primzahl.

Unsere Aussage und die Kontraposition der Aussage sind äquivalent. Beweise ich die Kontraposition, ist die ursprüngliche Aussage ebenfalls wahr.

Answer 2

[AusMeinemAlltag]

Wenn n keine Primzahl ist, dann muss gelten:

n = a * b, mit a > 1 und b > 1

Und wenn das der Fall ist, dann lässt sich

2 ^ (a * b) - 1 sowohl durch (2 ^ a) - 1 als auch durch (2 ^ b) - 1 teilen, kann also keine Primzahl sein.

Woher ich das weiß: Recherche

Comments

[Todaboi]

Wieso lässt sich 2 ^ (a * b) - 1 durch (2 ^ a) - 1 bzw  (2 ^ b)-1teilen. ?

[FataMorgana2010]

@Todaboi

Das hast du doch selber geschrieben, dass du das aus der vorherigen Aufgabe hast, wie sich 2^(ab) - 1 als Produkt schreiben lässt...

[Todaboi]

@FataMorgana2010

Stimmt, ich bin jetzt bissle verwirrt, ich hab damit doch die Kontraposition bewiesen. Wie drücke ich jetzt aus, dass ich die Aussage eine Zahl n aus der natürlichen Zahlen ist eine Primzahl, wenn 2^n -1 eine Primzahl ist bewiesen haben, Sorry bin irgendwie selber verwirrt