Summe zweier Quadrate bestimme < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:55 So 21.08.2011 | | Autor: | can19 |
| Aufgabe | Erläutern sein ein allgemeingültiges Verfahren, mit dem eine solche Darstellung von 233 als Summe zweier Quadrate [mm] x^{2}+y^{2} [/mm] ermittelt werden kann, und ermitteln sie damit eine solche Darstellung.
Hinweis: [mm] 89^{2}\equiv [/mm] -1 mod 233 |
Hallo
ich habe diese Aufgabe in einer Klausur gefunden.
Ich weiß leider kein Verfahren außer Ausprobieren.
Dass 233 als Summe zweier Quadrate darstellbar ist folgt aus der Bedingung:
[mm] 233\not\equiv [/mm] 3 mod 4
Ich habe raus 233= 8² + 13²
aber wie kommt man schneller auf die Lösung?
und was hilft mir der Hinweis?
lg
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:42 So 21.08.2011 | | Autor: | hippias |
Es irritiert mich das "eine solche Darstellung" in der Problemstellung. Was ist mit solche gemeint? Einfach die Darstellung als Summe zweier Quadratzahlen?
Auf die Schnelle haette ich folgende Idee fuer eine Verfahren: Es geht zwar nicht ohne Durchprobieren, aber wenigstens kann ich den Hinweis gebrauchen.
Wenn [mm] x^{2}+ y^{2}= [/mm] 233, so ist [mm] y^{2}= -x^{2} [/mm] mod 233 und aus [mm] 233\not\vert [/mm] x folgt [mm] (yx^{-1})^{2}= [/mm] -1 mod 233. Da 233 eine Primzahl ist -hoffe ich - besitzt die Gleichung [mm] t^{2}= [/mm] -1 nur die Loesungen 89 und -89 mod 233 (siehe Hinweis). Folglich muss y= 89x oder y= -89 x mod 233 gelten.
Damit braucht man nur noch fuer x die Zahlen von 1...233 durchprobieren, waehrend y sich wie oben ergibt (der Fall y= -89x mod 233 ist dann in y= 89x mod 233 enthalten).
Sonst faellt mir noch ein Satz ein, der besagt, wenn sich n und p als Summe von zwei Quadratzahlen darstellen lassen und wenn n= kp ist, dann laesst sich auch k als Summe zweier Quadratzahlen darstellen und diese Darstellung laesst sich einfach aus denen von n und p berechnen.
D.h. [mm] 89^{2}+ 1^{2}= [/mm] 34*233, wobei 34= 2*17. Nun ist 2= [mm] 1^{2}+ 1^{2} [/mm] und 17= [mm] 4^{2}+ 1^{2}, [/mm] sodass sich eine Darstellung von 233 im Prinzip leicht errechnen liesse, wenn mir der Satz im Detail erinnerlich waere.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:29 So 21.08.2011 | | Autor: | felixf |
Moin!
> Es irritiert mich das "eine solche Darstellung" in der
> Problemstellung. Was ist mit solche gemeint? Einfach die
> Darstellung als Summe zweier Quadratzahlen?
Ich denke das ist gemeint.
> Auf die Schnelle haette ich folgende Idee fuer eine
> Verfahren: Es geht zwar nicht ohne Durchprobieren, aber
> wenigstens kann ich den Hinweis gebrauchen.
> Wenn [mm]x^{2}+ y^{2}=[/mm] 233, so ist [mm]y^{2}= -x^{2}[/mm] mod 233 und
> aus [mm]233\not\vert[/mm] x folgt [mm](yx^{-1})^{2}=[/mm] -1 mod 233. Da 233
> eine Primzahl ist -hoffe ich - besitzt die Gleichung [mm]t^{2}=[/mm]
> -1 nur die Loesungen 89 und -89 mod 233 (siehe Hinweis).
> Folglich muss y= 89x oder y= -89 x mod 233 gelten.
> Damit braucht man nur noch fuer x die Zahlen von 1...233
> durchprobieren, waehrend y sich wie oben ergibt (der Fall
> y= -89x mod 233 ist dann in y= 89x mod 233 enthalten).
Man muss eigentlich viel weniger probieren: aus [mm] $x^2 [/mm] + [mm] y^2 [/mm] = 233$ und $x, y [mm] \ge [/mm] 0$ folgt $x [mm] \le \lfloor\sqrt{233}\rfloor [/mm] = 15$. Du musst also nur $x = 0, [mm] \dots, [/mm] 15$ durchprobieren, und fuer jede Wahl von $x$ schauen, ob [mm] $\srqt{233 - x^2}$ [/mm] eine ganze Zahl ist. (Und $x = 0$ kann man weglassen, da 233 kein Quadrat ist.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:46 So 21.08.2011 | | Autor: | hippias |
> jede Wahl von [mm]x[/mm] schauen, ob [mm]\srqt{233 - x^2}[/mm] eine ganze
> Zahl ist. (Und [mm]x = 0[/mm] kann man weglassen, da 233 kein
Ich nehme an Du meintest "eine Quadratzahl". Da uebrigens eine der beiden Zahlen =0 mod 4 ist, bleiben sogar nur die Moeglichkeiten x= 4,8,12 uebrig.Da ferner 233=-1 mod 3 und -1 kein Quadrat mod 3 ist, scheidet auch 12 aus.
|
|
|
|
