Primzahl als Summe zweier Quadrate

25.05.2012, 23:02

ChilliJilli

Auf diesen Beitrag antworten »

Primzahl als Summe zweier Quadrate

Huhu,

Ich soll die Primzahl $\begin{eqnarray*} p=2^{47}+5 \end{eqnarray*}$ als Summe zweier Quadrate darstellen, sodass a²+b²=p.

Ich weiß, dass $\begin{eqnarray*} p=2^{47}+5 = 140 737 488 355 333 \end{eqnarray*}$ also
$\begin{eqnarray*} = 4* 35 184 372 088 833 + 1 \end{eqnarray*}$

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

$\begin{eqnarray*} u^2 \equiv -1 \mod p \end{eqnarray*}$

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 Big Laugh

Big Laugh

26.05.2012, 00:38

Mystic

Auf diesen Beitrag antworten »

Hm, nicht gleich am Anfang schlapp machen... Big Laugh

Big Laugh

Das ist ja noch echt leicht: Nimm irgendein ganzes a her und schau nach, ob

$\begin{eqnarray*} a^{\frac {p-1}2} \equiv -1 \mod p \end{eqnarray*}$

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... Forum Kloppe

Forum Kloppe

Hier dein Schluss ausführlich angeschrieben, damit du den Riesenbock, den du da abgeschossen hast, selber sehen kannst... unglücklich

unglücklich

$\begin{eqnarray*} p \equiv 1 \mod 4 \Rightarrow \frac {p-1}2 \text{ ist gerade} \Rightarrow (-1)^{\frac {p-1}2} \equiv -1 \mod p \text{ !!!} \end{eqnarray*}$

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! Big Laugh

Big Laugh

) und berechne dann

$\begin{eqnarray*} a^{\frac{p-1}2} \mod p \end{eqnarray*}$

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... Big Laugh

Big Laugh

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:

$\begin{eqnarray*} 2^{(p-1)/2} \equiv -1 \mod p \end{eqnarray*}$

und ausserdem ist (p-1)/2, wie schon gesagt wurde, gerade(!)... Was könnte daher das gesuchte u sein, für das gilt

$\begin{eqnarray*} u^2 \equiv -1 \mod p \end{eqnarray*}$

Das sollte aber jetzt wirklich nicht schwer sein... Augenzwinkern

Augenzwinkern

26.05.2012, 12:21

ChilliJilli

Auf diesen Beitrag antworten »

hm ok also es müsste gelten

$\begin{eqnarray*} ((2 hoch(p-1)/4)^{2} \equiv -1 \mod p \end{eqnarray*}$

(sry anders konnte ich's nicht eingeben)

26.05.2012, 12:29

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von ChilliJilli
hm ok also es müsste gelten

$\begin{eqnarray*} (2^{(p-1)/4})^{2} \equiv -1 \mod p \end{eqnarray*}$

aber der Rechner schafft es nicht das zu überprüfen

Was meinst du damit? Dein Rechner schafft die Berechnung von

$\begin{eqnarray*} u:=2^{(p-1)/4} \mod p \end{eqnarray*}$

nicht? geschockt

geschockt

Mein Rat: Überprüf entweder deine Eingabe oder nimm einen anderen... Big Laugh

Big Laugh

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? verwirrt

verwirrt

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... Freude

Freude

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 $\begin{eqnarray*} r< \sqrt p \end{eqnarray*}$ 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 $\begin{eqnarray*} r_{n} \end{eqnarray*}$ die Folge: $\begin{eqnarray*} r_{0}=p, r_{1}=x, r_{n}=r_{n-2}mod \ r_{n-1} \end{eqnarray*}$
Sei l der kleinste Index, sodass $\begin{eqnarray*} r_{l}<\sqrt{p} \end{eqnarray*}$ Dann ist $\begin{eqnarray*} p - r_{l}² \end{eqnarray*}$ = 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? verwirrt

verwirrt

Edit: Und ja, die Bedingung u>p/2, die hier aber erfüllt ist, hatte ich tatsächlich vergessen... unglücklich

unglücklich

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 $\begin{eqnarray*} p- r_{20}² =48334294530369 = 6952287² \end{eqnarray*}$

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! Gott

Gott

26.05.2012, 13:33

Mystic

Auf diesen Beitrag antworten »

Gerne! Ende gut, alles gut... Wink

Wink

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »