Beweis von Primzahl

Neue Frage »

sabii22 Auf diesen Beitrag antworten »
Beweis von Primzahl
Meine Frage:
Es gelte und woebi die p_i die PFZ von n-1 ist und a eine Natürliche Zahl.

Z.z ist, dass n eine Primzahl ist.

Meine Ideen:
Würde die ORdnung von a berechnen (in Z/nZ)^x aber ich bin mir nicht sicher, ob es nicht eine kleiner Zahl als n-1 geben kann die a^x=1 mod(n) erfüllt.
HAL 9000 Auf diesen Beitrag antworten »

Es ist kaum anzunehmen, dass die Primfaktorzerlegung von ist. Kann es sein, dass du den Satz an der Stelle total inhaltlich verstümmelt hast und eigentlich folgendes gemeint ist:

Zitat:
Es gelte und für jeden Primteiler von , sowie sei eine natürliche Zahl.

Z.z ist, dass eine Primzahl ist.
sabii22 Auf diesen Beitrag antworten »

Schlecht ausgedrückt: p_1 ,...,p_n ist die PFZ von n-1
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von sabii22
ob es nicht eine kleiner Zahl als n-1 geben kann die a^x=1 mod(n) erfüllt.

Fermat-Euler ist bekannt? Da hier teilerfremd sind (wäre auch noch zu begründen!), gilt auch . Und wenn keine Primzahl ist, dann gilt sicher . Und daraus kann letztlich auch ein indirekter Beweis gebaut werden.
sabii22 Auf diesen Beitrag antworten »

Ich soll also versuchen aus
(Annahme n ist keine Primzahl) ein Widerspruch zu konstruieren? verwirrt
sabii22 Auf diesen Beitrag antworten »

Fermat-Euler ist bekannt.
 
 
HAL 9000 Auf diesen Beitrag antworten »

Ich würde den Beweis so aufbauen: Zunächst mal betrachten wir nur (ist womöglich vorausgesetzt, ansonsten muss man sich Gedanken machen, was man im Fall n=1 überhaupt mit der Primfaktorzerlegung von n-1=0 meint...)

1) Begründen, dass teilerfremd sind.

2) Aus sowie folgern, dass auch für gilt.

3) Fall keine Primzahl ist, gilt und damit auch . Aus diesem kann man dann einen Widerspruch zur Voraussetzung " für alle Primteiler von " basteln.
sabii22 Auf diesen Beitrag antworten »

Ich finde da leider den Widerspruch zu der von dir genannten Voraussetzung nicht. verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Wir wissen für ein , welches nicht nur kleiner als , sondern auch ein Teiler von ist.

Andererseits ist für alle Primteiler von vorausgesetzt.

Aus beidem zusammen kannst du keinen Widerpruch konstruieren? Denk nochmal nach.
sabii22 Auf diesen Beitrag antworten »

Wenn m n-1 teilt dann teilt m auch einen Primfaktor p von n-1, aber der letzte Sprung fehlt mir.
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von sabii22
dann teilt m auch einen Primfaktor p von n-1

muss ja nicht mal Primzahl sein, wie kann dann dieses teilen? unglücklich

Nein, wir suchen eine Primzahl derart, dass ein Teiler von ist, und das geht ja einfach so: Da ein echter Teiler von ist, gibt es eine Primzahl mit , folglich ist eine ganze Zahl. Es folgt



schon haben wir den Widerspruch, denn laut Voraussetzung muss ja ungleich 1 herauskommen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »