p prim, p = 3 (mod 4) => p teilt nicht n^2+1??

20.01.2006, 19:47

Brox

p prim, p = 3 (mod 4) => p teilt nicht n^2+1??

Hier die Frage nochmal:

Sei p eine Primzahl mit p mod 4 = 3. Dann gibt es keine natürliche Zahl n so, dass n^2+1 durch p teilbar ist.

Mit dieser Frage bin ich total überfordert - obwohl sie so leicht aussieht...

- Peter

20.01.2006, 19:53

JochenX

Auf diesen Beitrag antworten »

RE: p prim, p = 3 (mod 4) => p teilt nicht n^2+1??

Zitat:

Original von Brox
Hier die Frage nochmal:

wieso NOCHMAL?
steht sie schon hier oder in einem anderen matheforum??

20.01.2006, 19:56

Brox

Auf diesen Beitrag antworten »

RE: p prim, p = 3 (mod 4) => p teilt nicht n^2+1??
Nein. Werf aber bitte noch einen Blick auf das Thema...

dieses Problem ist frustrierend

20.01.2006, 20:22

Auf diesen Beitrag antworten »

Zitat:

Original von Brox
obwohl sie so leicht aussieht...

Hängt ganz vom Vorwissen ab, würde ich sagen. Ohne gewisse Zahlentheoriekenntnisse ist die Aufgabe schon ziemlich schwer.

Kennst du das Qudaratische Reziprozitätsgesetz, und da insbesondere den 1.Ergänzungssatz? Damit ist es dann allerdings ein Kinderspiel.

20.01.2006, 21:40

Brox

Auf diesen Beitrag antworten »

Quad. rezi.
hmm der Satz sagt mir nichts. Und auch beim überfliegen hab ich nur komische Symbole und Klammer gesehen... Aber -

Wie siehts hiermit aus:

Ann: p teilt n^2+1

also:
n^2+1 = 0 (mod p)
n^2 = -1 (mod p)
n^2 = p - 1 (mod p)
!
n^4 = 1 (mod p)
!!

und nach dem kleinen Satz von fermat gilt:

n^(p-1) = 1 (mod p)

so. Jetzt habe ich alle Vorbedingungen Eingebaut... Sollte sich doch jetzt von alleine beweisen lassen. Na mal sehen:

folgt aus n^(p-1) = 1 (mod p) und n^4 = 1 (mod p), dass p-1 mod 4 = 0?? das wäre natürlich ein klarer wiederspruch zu p mod 4 = 3...

hmm kann das jemand entschlüsseln?

20.01.2006, 21:47

Auf diesen Beitrag antworten »

Ja, gute Idee, du hast eigentlich schon alles wichtige dastehen, dir fehlt nur noch die richtige Verbindung:

Falls $\begin{eqnarray*} p\equiv 3\mod 4 \end{eqnarray*}$ , dann ist $\begin{eqnarray*} p=4k+3 \end{eqnarray*}$ mit irgendeiner ganzen Zahl $\begin{eqnarray*} k \end{eqnarray*}$ . Von $\begin{eqnarray*} n^2\equiv -1\mod p \end{eqnarray*}$ ausgehend folgt also

$\begin{eqnarray*} n^{p-1} = n^{4k+2} = (n^2)^{2k+1} \equiv (-1)^{2k+1} = -1\mod p \end{eqnarray*}$

und das ergibt jetzt verglichen mit dem Fermat einen Widerspruch.

20.01.2006, 21:51

Brox

Auf diesen Beitrag antworten »

Ok
danke

ich weiß schon warum das hier mein letzter mathe Kurs sein wird ^^

aber die Hilfe war prima nochmal danke

20.01.2006, 22:16

Brox

Auf diesen Beitrag antworten »

hmmm
Aufgabe:
"Lösen Sie die Gleichung:
17*X=1 mod 3^7*13^4*4*7"

Antwort: 17^(phi(modul)-1)

reicht das? Auf mehr habe ich nämlich gar keine lust. Aber wenn es wirklich gravierend ist, rappele ich mich nochmal auf.

21.01.2006, 00:26

Auf diesen Beitrag antworten »

Keine Ahnung, ob das deinem Aufgabensteller reicht. Aber den Exponent $\begin{eqnarray*} \varphi(2^2\cdot 3^7\cdot 7\cdot 13^4)-1 \end{eqnarray*}$ könntest du ja wenigstens noch ausrechnen.

Aber warum löst du das nicht auf einfache Weise: Mit $\begin{eqnarray*} M = 2^2\cdot 3^7\cdot 7\cdot 13^4 \end{eqnarray*}$ bedeutet $\begin{eqnarray*} 17x \equiv 1 \mod M \end{eqnarray*}$ einfach $\begin{eqnarray*} 17x = 1 + Mk \end{eqnarray*}$ mit einer ganzen Zahl $\begin{eqnarray*} k \end{eqnarray*}$ . Modulo 17 ergibt das $\begin{eqnarray*} 0 \equiv 1+2k\mod 17 \end{eqnarray*}$ , also $\begin{eqnarray*} k \equiv 8\mod 17 \end{eqnarray*}$ .

Es ergibt sich dann $\begin{eqnarray*} x \equiv \frac{1+8M}{17} \mod M \end{eqnarray*}$ .

22.01.2006, 14:07

Brox

Auf diesen Beitrag antworten »

hmmm
Hast Du
$\begin{eqnarray*} M \mod 17 = 2 \end{eqnarray*}$
so ausgerechnet:
$\begin{eqnarray*} M=4*27*27*3*7*169*169=4*10*10*3*7*16*16= \end{eqnarray*}$

$\begin{eqnarray*} 40*30*112*16=6*13*10*16=78*160=10*7=70=2 (\mod 17) \end{eqnarray*}$
?? Oder gibts da einen Trick?

22.01.2006, 18:46

Auf diesen Beitrag antworten »

Einen richtigen Trick gibt es nicht, man kann natürlich mehr oder weniger geschickt die Potenzen modulo 17 umformen, z.B. so

$\begin{eqnarray*} M &=& 2^2 \cdot (3^2)^3 \cdot (3\cdot 7) \cdot 13^4 \equiv 2^2 \cdot (-8)^3 \cdot 4 \cdot (-4)^4\\ &=& -2^{21} = -2\cdot 16^5 \equiv -2\cdot (-1)^5 = 2\mod 17 \end{eqnarray*}$

Aber das ist letztendlich Geschmackssache. Augenzwinkern

22.01.2006, 19:04

Brox

Auf diesen Beitrag antworten »

hmm ich hab aber nochmal über das problem nachgedacht und die Lösung x=(1+8M)/17 kann man auch nur durch realtiv viel rechen rauskriegen - das ist schonmal eine Verbesserung zu 17^(phi(M)-1) wo man nichtmal ein richtiges Ergebnis rauskriegt - aber weil M so groß ist - kann das Ergebnis wirklich nur durch eine sehr große Rechnung rausbekommen werden, richtig? Ich meine ich hab überlegt ob man nicht die simultanen kongruenzen 17x=1 (mod 3^7), 17x=1 (mod 13^4) durch den euklidischen Algorithmus ausrechnen könnte - aber die Terme die man da dann kriegt... traurig

Ich versuche die Rechnung immer so einfach zu machen, dass ich eine änliche Aufgabe auf anhieb ohne Fehler aufschreiben kann. Ich glaube das hier ist die erste Aufgabe bei der ich das nicht hinkriege...

22.01.2006, 19:12

Auf diesen Beitrag antworten »

Nun übertreib mal nicht, so groß sind die Zahlen nun auch wieder nicht:

$\begin{eqnarray*} M &=& 1748961396\\ \frac{1+8M}{17} &=& 823040657 \end{eqnarray*}$

(Mein Taschenrechner hat jedenfalls noch keine Probleme, obwohl es hart an der Grenze ist.) Und wenn die Zahlen größer werden, dann ist die Frage, mit welcher Lösungsdarstellung dein Aufgabensteller sich zufrieden gibt...

25.01.2006, 21:45

Brox

Auf diesen Beitrag antworten »

Heute hab ich von meiner Tutorin folgenden merkwürdigen Hinweis bekommen:
"
Hallo!

Zu Aufgabe 2: # das ist die Aufgabe: löse 17X = 1 mod 3^7*13^4*4*7
Diese Aufgabe soll doch mit der phi-Funktion bearbeitet werden.
==> phi(n) [fuer das richtige n] ausrechnen, und dann ein X angeben, und
BEGRUENDEN, warum dieses X die Gleichung erfuellt, und warum "kein"
anderes X dies tut.

Viel Spass dabei
"

Vor allem der letzte Relativsatz kommt mir komisch vor. Ich meine wir haben doch mindestens zwei Lösungen oder? Ich meine 17^(phi(M)-1) und (1+8M)/17. Das multiplikative inverse zu 17 zum modul M muss ja nicht eindeutig sein - wenn 17 und M teilfremd sind ist damit doch nur die exsitens gesichert.

@Arthur nochmal dankeschön. Ich hab noch eine Frage wie Du auf die Lösung gekommen bist. Hast Du "auf Verdacht" M mod 17 ausgerechnet?

25.01.2006, 21:49

Auf diesen Beitrag antworten »

Zitat:

Original von Brox
Ich meine wir haben doch mindestens zwei Lösungen oder? Ich meine 17^(phi(M)-1) und (1+8M)/17.

Korrektur: Wir haben zwei Darstellungen ein und derselben Lösung!
Das multiplikative inverse zu 17 zum modul M ist eindeutig, da 17 und M teilerfremd sind.

25.01.2006, 22:18

Brox

Auf diesen Beitrag antworten »

Ja die Eindeutigkeit ist ziemlich klar.

Tut mir leid für die dumme Frage ><

Neue Frage »

Antworten »

p prim, p = 3 (mod 4) => p teilt nicht n^2+1??

Verwandte Themen