Zahlentheorie: Beweis für n|((n-1)!+1) => n € |P (n>1)

Neue Frage »

therisen Auf diesen Beitrag antworten »
Zahlentheorie: Beweis für n|((n-1)!+1) => n € |P (n>1)
Hi,
folgendes ist zu beweisen: Sei n eine natürliche Zahl, . Aus folgt .

Ich entscheide mich für den direkten Beweis, denn ich meine die vollständige Induktion macht hier keinen Sinn und für einen Widerspruchsbeweis fällt mir nichts ein.

Zunächst eine Umformung:

Ist keine Primzahl, so folgt zwangsläufig die Zerlegbarkeit in (Prim)faktoren. lässt sich folglich als darstellen, vorausgesetzt n ist ein Teiler von . Daraus folgt: . Also forme ich um: . Jetzt kommt der Teil, wo ich mir nicht ganz sicher bin, ob das korrekt ist. Ich sage, , denn es ist ja ein Teiler von . Nun wende ich das Fundamentallemma an: . qed.
Ich bitte um Meinungen und falls mein Beweis falsch ist, einen kleinen Gedankenanstoß. Danke.

Gruß, therisen
Leopold Auf diesen Beitrag antworten »

Ich glaube, dein Beweis ist ziemlich falsch. Du sollst ja zeigen, daß aus einer Teilbarkeitsbeziehung für n folgt, daß n eine Primzahl ist.

Schon den Anfang verstehe ich nicht: "Ist (n!/n)+1 keine Primzahl, ..."
Wie kannst du das einfach annehmen? So etwas ist doch gar nicht vorausgesetzt! (Für n=2 oder n=3 ist das z.B. eine Primzahl, später allerdings nicht mehr. Das wäre aber zu begründen.)
Allerdings ist richtig, daß (n!/n)+1=d·n gilt, denn das ist ja gerade vorausgesetzt.


Du solltest dir erst noch einmal ganz klar machen:
Was ist die Voraussetzung?
Was ist die Behauptung?

Für den Beweis würde ich indirekt vorgehen, also: Für eine zusammengesetzte Zahl n kann die Teilbarkeitsbedingung nicht gelten.
Beachte, daß sich jede zusammengesetze Zahl n schreiben läßt als

mit nicht notwendigerweise verschiedenen Primzahlen und und überlege, warum n dann ein Teiler von (n-1)! sein muß.

Die Umkehrung des zu beweisenden Satzes kennt man übrigens unter dem Namen Satz von Wilson.
Gustav Auf diesen Beitrag antworten »

Mängel in deinem Beweis wurden bereits erwähnt.
Hier ein alternativer Beweis:

Es sei p|(p-1)!+1. Ist und d|p, dann folgt d|(p-1)! und damit dann auch d|1, also d = 1. Daher ist p eine Primzahl.
q.e.d.

Umgekehrt:

p sei eine Primzahl > 2, so existiert eine primitive Restklasse [a] modulo p. Dann gilt:

mod p
Für ist mod p also p|(x+1)(x-1). Da [a] primitiv ist, gilt .
q.e.d.

Also ist p genau dann eine Primzahl, wenn p|(p-1)!+1.
therisen Auf diesen Beitrag antworten »

OK danke euch beiden, das hilft mir schon mal sehr viel weiter :] Leopolds Ratschläge werde ich nochmal intensiv durchdenken smile

Btw es ist erst mein 2. selbstständig formulierter Beweis, also bitte ich um Nachsicht traurig Ich muss erst noch ein Gefühl dafür bekommen, das ist doch normal oder?

Zitat:
Original von Gustav
Mängel in deinem Beweis wurden bereits erwähnt.
Hier ein alternativer Beweis:

Es sei p|(p-1)!+1. Ist und d|p, dann folgt d|(p-1)! und damit dann auch d|1, also d = 1. Daher ist p eine Primzahl.
q.e.d.

Genial. Ich habe nicht daran gedacht, dass sich eine Primzahl ja auch mit d=1 darstellen lässt :P Du hast die Regeln "Aus a|b und b|c folgt a|c" und "Aus a|b und a|c folgt a|(xb+yc) für alle x,y€Z" verwendet, um zu folgern, dass d|(p-1)! und d|1 ist oder?
Gustav Auf diesen Beitrag antworten »

Zitat:
Original von therisen
Du hast die Regeln "Aus a|b und b|c folgt a|c" und "Aus a|b und a|c folgt a|(xb+yc) für alle x,y€Z" verwendet, um zu folgern, dass d|(p-1)! und d|1 ist oder?


Allgemeiner gilt:

Aus a|b und a|c ... und ... a|z folgt
a|b+c+...+z

für alle

Deshalb folgt aus d|p, dass gilt d|(p-1)(p-2)...(p-(p-1)) und deshalb d|1.
Leopold Auf diesen Beitrag antworten »

@ Gustav
Bei deinem Beweis der Rückrichtung stimmt etwas nicht. Vielleicht handelt es sich nur um Schreibfehler. Meiner Meinung nach muß es so heißen:

... Für gilt mod p, also p|(x-1)(x+1). Da [a] primitiv ist, gilt .
 
 
Gustav Auf diesen Beitrag antworten »

Richtig, Leopold. Es handelt sich um Schreibfehler. smile
Neue Frage »
Antworten »



Verwandte Themen

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