p prim, p = 3 (mod 4) => p teilt nicht n^2+1?? |
20.01.2006, 19:47 | Brox | Auf diesen Beitrag antworten » | ||
p prim, p = 3 (mod 4) => p teilt nicht n^2+1?? 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??
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 | AD | Auf diesen Beitrag antworten » | ||
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 | AD | Auf diesen Beitrag antworten » | ||
Ja, gute Idee, du hast eigentlich schon alles wichtige dastehen, dir fehlt nur noch die richtige Verbindung: Falls , dann ist mit irgendeiner ganzen Zahl . Von ausgehend folgt also und das ergibt jetzt verglichen mit dem Fermat einen Widerspruch. |
||||
Anzeige | ||||
|
||||
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 | AD | Auf diesen Beitrag antworten » | ||
Keine Ahnung, ob das deinem Aufgabensteller reicht. Aber den Exponent könntest du ja wenigstens noch ausrechnen. Aber warum löst du das nicht auf einfache Weise: Mit bedeutet einfach mit einer ganzen Zahl . Modulo 17 ergibt das , also . Es ergibt sich dann . |
||||
22.01.2006, 14:07 | Brox | Auf diesen Beitrag antworten » | ||
hmmm Hast Du so ausgerechnet: ?? Oder gibts da einen Trick? |
||||
22.01.2006, 18:46 | AD | 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 Aber das ist letztendlich Geschmackssache. |
||||
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... 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 | AD | Auf diesen Beitrag antworten » | ||
Nun übertreib mal nicht, so groß sind die Zahlen nun auch wieder nicht: (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 | AD | Auf diesen Beitrag antworten » | ||
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 >< |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|