Primzahl als Summe zweier Quadrate |
25.05.2012, 23:02 | ChilliJilli | Auf diesen Beitrag antworten » | ||
Primzahl als Summe zweier Quadrate Ich soll die Primzahl als Summe zweier Quadrate darstellen, sodass a²+b²=p. Ich weiß, dass also Also ist die Zerlegung nach Fermat möglich. Leider habe ich gar keine Ahnung wie ich das machen soll. Bei kleineren Primzahlen kann man das ja durch ausprobieren rausbekommen, aber bei dieser? |
||||
25.05.2012, 23:48 | Mystic | Auf diesen Beitrag antworten » | ||
RE: Primzahl als Summe zweier Quadrate Tja, das ist nicht so ganz einfach... Als erstes brauchst du ein u, das die Bedingung erfüllt... Wenn du ein solches gefunden hast, dann sag ich dir, wie's weiter geht... |
||||
26.05.2012, 00:12 | ChilliJilli | Auf diesen Beitrag antworten » | ||
uh ok schon das ist eine Herausforderung für mich, aber ich versuchs jetzt mal. Wenigstens ein Tip in welche Richtung ist suchen muss |
||||
26.05.2012, 00:38 | Mystic | Auf diesen Beitrag antworten » | ||
Hm, nicht gleich am Anfang schlapp machen... Das ist ja noch echt leicht: Nimm irgendein ganzes a her und schau nach, ob ist... Die Chancen dafür stehen fifty-fifty... Ich hoffe, du weißt dann selbst, wie du zu dem gesuchten u kommst... |
||||
26.05.2012, 01:07 | ChilliJilli | Auf diesen Beitrag antworten » | ||
Ich hab echt keine Ahnung -.- Ich habs bis jetzt nur durch ausprobieren getestet, was bei den Zahlen gar nicht so leicht ist, da der Rechner dauernd nicht will... warum denn jetzt auf einmal dieser a Term? Wenn ich's mit a=-1 teste bekomme ich mod p das richtige -1 raus, aber wie kann das was für die Suche nach u² helfen? Bei lesen in Foren u.s.w. hab ich glaub ich gelesen, dass (p-1)/2 das Inverse von 2 modulo p ist oder so und irgendwas mit diesem Legendre-Symbol. Das hatten wir aber alles noch nicht in der Vorlesung - ich hab also gar keine Ahnung davon. Wir hatten auch in der Vorlesung nur den Satz, dass ein u²=-1 mod p für so ein p wie hier existiert, aber nicht, wie man es bestimmt und alles was ich in Foren dazu finden konnte war mir ausreichend kleinen p sodass man es probieren konnte... |
||||
26.05.2012, 09:50 | Mystic | Auf diesen Beitrag antworten » | ||
Au weia, das wird eine sehr zähe Angelegenheit, weil du nicht nur nicht bereit bist, ein bißchen mitzudenken, sondern auch bei deinen wenigen Überlegungen zur Sache katastrophale Fehler machst... Hier dein Schluss ausführlich angeschrieben, damit du den Riesenbock, den du da abgeschossen hast, selber sehen kannst... Nimm doch endlich irgendein CAS her (wenn du noch keines hast, dann gibt's auch welche gratis im Internet wie z.B. Maxima), nimm irgendeine ganze Zahl a (aber bitte nicht ausgerechnet a=-1, und auch nicht a=0 und auch nicht a=1, falls das weitere Kandidaten bei dir wären! ) und berechne dann Wenn dabei 1 statt -1 mod p herauskommt, hast du Pech gehabt, und musst ein neues a wählen... Im Falle, dass es ein "richtiges " a war, wie kannst du dann daraus das gesuchte u gewinnen? Ich hoffe, das klappt nach diesem desaströsen Start jetzt endlich, denn das war ja eigentlich nur zum "Aufwärmen" gedacht, die eigentliche Aufgabe kommt ja noch... |
||||
Anzeige | ||||
|
||||
26.05.2012, 11:47 | ChilliJilli | Auf diesen Beitrag antworten » | ||
Oh Mann ... Sry bin echt blöd Ich habs jetzt nochmal mit einem online-Rechner gemacht - der ist nicht soo überfordert mit den Zahlen und hab für a mögliche Lösungen gefunden: für z.B. a=2 und 5 und 6 Ich habe nur leider keine Ahnung wie mir das helfen soll das gesuchte x² zu finden, dass kongruent zu -1 modulo p sein soll, aber ich suche weiter danach |
||||
26.05.2012, 12:07 | Mystic | Auf diesen Beitrag antworten » | ||
Ok, also halten wir fest: und ausserdem ist (p-1)/2, wie schon gesagt wurde, gerade(!)... Was könnte daher das gesuchte u sein, für das gilt Das sollte aber jetzt wirklich nicht schwer sein... |
||||
26.05.2012, 12:21 | ChilliJilli | Auf diesen Beitrag antworten » | ||
hm ok also es müsste gelten (sry anders konnte ich's nicht eingeben) |
||||
26.05.2012, 12:29 | Mystic | Auf diesen Beitrag antworten » | ||
Was meinst du damit? Dein Rechner schafft die Berechnung von nicht? Mein Rat: Überprüf entweder deine Eingabe oder nimm einen anderen... |
||||
26.05.2012, 12:39 | ChilliJilli | Auf diesen Beitrag antworten » | ||
hm ja so als ganzen Term hatte er das nicht geschafft, aber in zwei Schnitten gings dann und es ist wahr, deswegen hatte ich meinen Beitrag diesbezüglich auch nochmal editiert. |
||||
26.05.2012, 12:50 | Mystic | Auf diesen Beitrag antworten » | ||
Hm, hast du nun endlich das u berechnen können und wie sieht es aus? |
||||
26.05.2012, 12:52 | ChilliJilli | Auf diesen Beitrag antworten » | ||
Also ich weiß jetzt: p=140 737 488 355 333 u=135 266 949 219 698 und p|u²+1² |
||||
26.05.2012, 12:56 | Mystic | Auf diesen Beitrag antworten » | ||
Wow! Die erste vernünftige Antwort seit Beginn des Threads... Das wurde aber auch Zeit, ich war schon nahe dran, das Handtuch zu werfen... Es geht also nun weiter damit, dass du den euklidischen Algorithmus auf p und u solange anwenden musst, bis erstmals der Rest ist... Kannst du das mal vorführen? |
||||
26.05.2012, 13:03 | ChilliJilli | Auf diesen Beitrag antworten » | ||
Wir hatte in der Vorlesung folgenden Satz: Sei p ungerade Primzahl und x²=-1modp mit (p/2)<x<p. Es bezeichne die Folge: Sei l der kleinste Index, sodass Dann ist = einer Quadratzahl. Kann ich den jetzt hier anwenden? Das wäre glaub ich das, was der Dozent im Sinn hatte... |
||||
26.05.2012, 13:05 | Mystic | Auf diesen Beitrag antworten » | ||
Hm, hab ich nicht oben genau das gesagt, aber halt nur mit meinen Worten und vermutlich auch etwas einprägsamer? Edit: Und ja, die Bedingung u>p/2, die hier aber erfüllt ist, hatte ich tatsächlich vergessen... |
||||
26.05.2012, 13:22 | ChilliJilli | Auf diesen Beitrag antworten » | ||
140737488355333 #r0 135266949219698 #r1 5470539135635 #r2 3974009964458 #r3 1496529171177 #r4 980951622104 #r5 515577549073 #r6 465374073031 #r7 50203476042 #r8 13542788653 #r9 9575110083 #r10 3967678570 #r11 1639752943 #r12 688172684 #r13 263407575 #r14 161357534 #r15 102050041 #r16 59307493 #r17 42742548 #r18 16564945 #r19 9612658 #r20 Also Und ja das hattest du hattest es schon gesagt - hab es bloß anfangs gar nicht kapiert und als du das mit dem euklidischen algorithmus getippt hattest, war ich sowieso grad dabei den Satz abzutippen und anzuwenden. Ich hatte auch anfangs gar keine Ahnung wie ich an so ein x² kommen sollte. Jetzt gilt also für p=a²+b² a=9612658 b=6952287 |
||||
26.05.2012, 13:31 | ChilliJilli | Auf diesen Beitrag antworten » | ||
Vielen vielen Dank für deine Geduld! |
||||
26.05.2012, 13:33 | Mystic | Auf diesen Beitrag antworten » | ||
Gerne! Ende gut, alles gut... |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|