Allgemeine Primteiler

08.11.2008, 01:32

Bjoern1982

Allgemeine Primteiler

Hallo,

sei n aus IN mit n>1 und N=2(n!)²-1

a) Bestimme für jeden Primteiler p von N ob 2 quadratischer Rest modulo p ist

b) Zeige, dass N einen Primteiler der Form p=8k-1 mit k aus IN besitzt

c) Zeige, dass es unendlich viele Primzahlen der Form 8k-1 mit k aus IN gibt

Meine Ansätze:

a) Auffällig ist ja gerade die 2, ich dachte da an den Zusammenhang $\begin{eqnarray*} \begin{pmatrix} 2 \\ p \end{pmatrix} =\begin{cases} 1 & \text{wenn }\ p \equiv\ \pm 1\ mod\ 8\\ -1 & \text{wenn}\ p \equiv\ \pm 3\ mod\ 8\end{cases} \end{eqnarray*}$ also der Benutzung des Legendre Symbols, jedoch würde ich damit ja schon p=8k-1 benutzen...

b) Da n mindestens 2 ist steckt in 2(n!)² in jedem Fall 2³=8, ist N womöglich sogar immer prim ? Wenn man das nachweisen würde, wäre in a) 2 in jedem Fall immer quadratischer Rest mod p

c) weiss ich leider nicht...vermutlich wieder durch einen indirekten Beweis

Kann mir jemand helfen ?

Gruß Björn

08.11.2008, 08:52

Auf diesen Beitrag antworten »

Das ist doch eine äußerst freundlich formulierte Aufgabe, die einem beim Lösen schön an die Hand nimmt. a) und b) geben doch deutliche Hilfestellung, wie man c) lösen kann. Jedenfalls wäre die alleinige Aufgabe

Zitat:

Original von Bjoern1982
Zeige, dass es unendlich viele Primzahlen der Form 8k-1 mit k aus IN gibt.

ohne diese Hilfestellungen um Längen schwieriger! Augenzwinkern

Das mit dem Zusammenhang $\begin{eqnarray*} \left( \frac{2}{p} \right) = \cdots \end{eqnarray*}$ ist eine richtige Idee, aber nicht für a), sondern für b) !

Bei a) kannst du doch einfach direkt nachweisen, dass 2 ein quadratischer Rest modulo $\begin{eqnarray*} p \end{eqnarray*}$ ist: Für $\begin{eqnarray*} a=2n! \end{eqnarray*}$ gilt

$\begin{eqnarray*} a^2 = 2(N+1) = 2N+2 \equiv 2 \mod p \end{eqnarray*}$ ,

für jeden Teiler $\begin{eqnarray*} p \end{eqnarray*}$ von $\begin{eqnarray*} N \end{eqnarray*}$ (also auch alle Primteiler) - fertig!

Zitat:

Original von Bjoern1982
ist N womöglich sogar immer prim ?

Das schlag dir mal aus dem Kopf, es gibt keine "einfachen" expliziten Formeln, die stets Primzahlen liefern. Im vorliegenden Fall nenne ich mal nur das Gegenbeispiel

$\begin{eqnarray*} 2\cdot (5!)^2 - 1 = 28799 = 31 \cdot 929 \end{eqnarray*}$ .

09.11.2008, 21:40

Bjoern1982

Auf diesen Beitrag antworten »

Zitat:

Bei a) kannst du doch einfach direkt nachweisen, dass 2 ein quadratischer Rest modulo $\begin{eqnarray*} p \end{eqnarray*}$ ist: Für $\begin{eqnarray*} a=2n! \end{eqnarray*}$ gilt...

Das passt echt prima für diese Wahl für a Augenzwinkern

Geht das nur durch genaues Hinschauen oder steckt da doch eine gewisse Systematik hinter, die einem gar keine andere Wahl lässt als dieses a zu wählen ?

Zitat:

Das mit dem Zusammenhang $\begin{eqnarray*} \left( \frac{2}{p} \right) = \cdots \end{eqnarray*}$ ist eine richtige Idee, aber nicht für a), sondern für b) !

Ok, nur dann müsste ich aber den Fall $\begin{eqnarray*} p \equiv +1\ mod\ 8 \end{eqnarray*}$ noch irgendwie auschließen oder ?

09.11.2008, 22:07

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Geht das nur durch genaues Hinschauen oder steckt da doch eine gewisse Systematik hinter, die einem gar keine andere Wahl lässt als dieses a zu wählen ?

Genaues Hinschauen. Augenzwinkern

Zitat:

Original von Bjoern1982
Ok, nur dann müsste ich aber den Fall $\begin{eqnarray*} p \equiv +1\ mod\ 8 \end{eqnarray*}$ noch irgendwie auschließen oder ?

Denk mal genauer nach: Aus a) sowie deiner Überlegung folgt, dass sämtliche Primfaktoren von N die Form $\begin{eqnarray*} \pm 1\mod 8 \end{eqnarray*}$ haben. In Kenntnis dieser Tatsache versuch doch mal, b) indirekt nachzuweisen...

10.11.2008, 13:30

Bjoern1982

Auf diesen Beitrag antworten »

Gut, also indirekt:

Angenommen N hätte keinen Primteiler p der Form 8k-1 (*)

Da wegen a) 2 in jedem Fall QR für jeden Primteiler p von N ist, müsste p wegen (*) von der Form 8k+1 sein.

Das muss ich ja jetzt zum Widerspruch führen, reicht es dann schon aus ein Gegenbeispiel zu bringen, also z.B. zu sagen, dass für n=2,3,4 in jedem Fall N prim ist, und somit selbst sein eigener Primteiler ist und da N selbst auch von der Form 8s-1 ist, kann p niemals immer von der Form 8k+1 sein.

Kann man das so machen ?

Zu c) habe ich mir überlegt, dass man zwar aus b) schonmal folgern kann, dass N immer p=8k-1 als einen Primteiler enthalten wird, man jedoch entweder noch zeigen müsste, dass "zwischendurch" in bestimmten Abständen immer mal wieder N selbst eine Primzahl ist, wodurch es dann mit Sicherheit unendlich viele Primteiler p=8k-1 geben wird.
Oder aber man zeigt, dass in der Primfaktorzerlegung von N auch immer "neue" Primfaktoren entstehen und keine Potenzen von "alten".

Oder denke ich da zu kompliziert und c) folgt trivialerweise schon aus a) und b) ?

10.11.2008, 13:43

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Das muss ich ja jetzt zum Widerspruch führen, reicht es dann schon aus ein Gegenbeispiel zu bringen, also z.B. zu sagen, dass für n=2,3,4 in jedem Fall N prim ist,

Nein, natürlich nicht. unglücklich

Du musst es für jedes n zum Widerspruch führen, dass N=2(n!)^2-1 nur Primteiler der Form 8k+1 hat.

Zitat:

Original von Bjoern1982
Zu c) habe ich mir überlegt, dass man zwar aus b) schonmal folgern kann, dass N immer p=8k-1 als einen Primteiler enthalten wird, man jedoch entweder noch zeigen müsste, dass "zwischendurch" in bestimmten Abständen immer mal wieder N selbst eine Primzahl ist,

Ich kann mir nur schwer vorstellen, wie man das beweisen kann.

AUch c) würde ich indirekt angehen: Angenommen, es gibt nur endlich viele Primzahlen der Form 8k-1. Dann gibt es unter denen auch eine größte, und mit Hilfe dieser größten Primzahl kann man nun ein passendes N angeben, dass durch keine der Primzahlen der Form 8k-1 teilbar ist...

10.11.2008, 14:10

Bjoern1982

Auf diesen Beitrag antworten »

Zitat:

Du musst es für jedes n zum Widerspruch führen, dass N=2(n!)^2-1 nur Primteiler der Form 8k+1 hat.

Für den allgemeinen Fall fehlt mir irgendwie die zündende Idee.
Was kann ich denn noch aus der Tatsache folgern, dass 8k+1 ein Primteiler von N ist ?
Ein Versuch noch Augenzwinkern

Da N von der Form 8z-1 ist muss (8k+1)*y=8z-1 gelten.
Modulo 8 würde das zu y<0 führen, was nicht sein kann, da alle Primteiler aus IN sind.

Ich geh schon Mal in Deckung *duck*

Zitat:

AUch c) würde ich indirekt angehen: Angenommen, es gibt nur endlich viele Primzahlen der Form 8k-1. Dann gibt es unter denen auch eine größte, und mit Hilfe dieser größten Primzahl kann man nun ein passendes N angeben, dass durch keine der Primzahlen der Form 8k-1 teilbar ist...

...was wegen b) ja nicht möglich ist ---> Widerspruch

Korrekt ?

10.11.2008, 14:19

Auf diesen Beitrag antworten »

Zitat:

Original von Bjoern1982
Da N von der Form 8z-1 ist muss (8k+1)*y=8z-1 gelten.
Modulo 8 würde das zu y<0 führen

Wieso y<0? Herrje, vielleicht meinst du ja das Richtige, aber du drückst dich einfach unmöglich aus. unglücklich

Wenn alle Primteiler kongruent 1 modulo 8 sind, dann ist auch deren Produkt (also N selbst!!!) kongruent 1 modulo 8 ... was aber wegen $\begin{eqnarray*} N\equiv -1 \mod 8 \end{eqnarray*}$ zum Widerspruch führt.

Zitat:

Original von Bjoern1982
...was wegen b) ja nicht möglich ist ---> Widerspruch

Richtig - aber von welchem N rede ich, und wieso ist das durch keine der genannten Primzahlen teilbar?

11.11.2008, 01:17

Bjoern1982

Auf diesen Beitrag antworten »

Ich kriegs irgendwie nicht auf die Reihe,also den Nachweis für c), aber anstatt da jetzt endlos lange drüber nachzudenken widme ich mich erstmal anderen Aufgaben smile

Danke dir.

11.11.2008, 08:37

Auf diesen Beitrag antworten »

Schade, entweder sieht man's, oder man sieht's eben nicht: Wenn $\begin{eqnarray*} q \end{eqnarray*}$ die größte dieser (8k-1)-Primzahlen ist, dann ist $\begin{eqnarray*} q! \end{eqnarray*}$ speziell auch durch alle (8k-1)-Primzahlen teilbar, und somit $\begin{eqnarray*} 2(q!)^2-1 \end{eqnarray*}$ durch keine dieser (8k-1)-Primzahlen teilbar, Widerspruch zu b).

11.11.2008, 18:45

Bjoern1982

Auf diesen Beitrag antworten »

Joa...muss man echt drauf kommen...wenn man es dann vor sich stehen hat sieht es immer ganz logisch aus Freude

Danke nochmal.

Neue Frage »

Antworten »

Allgemeine Primteiler

Verwandte Themen