Euclidean alg. in quadratic NF < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:02 Sa 01.05.2010 | | Autor: | Arcesius |
| Aufgabe | For the following pairs of algebraic integers (a,b) use the Euclidean alg. to find d = gcd(a,b), along with an expression ra + sb = d, for some algebraic integers r,s in the given quadratic number field
a) a = [mm] 23\sqrt{2} [/mm] - 15, b = [mm] 3\sqrt{2} [/mm] + 23 in [mm] \IQ(\sqrt{2}) [/mm] |
Hallo Zusammen
Ich verzweifle noch.. wir haben den Euclidischen algorithmus vor langer Zeit für ganze Zahlen gesehen... nun sollen wir den ggT von zwei algebraischen Zahlen in [mm] \IQ(\sqrt{d}) [/mm] finden..
Ich habe nun lange nach einer Vorgehensweise gesucht, doch erfolglos.. das meiste das ich gefunden habe waren hauptsächlich Papers über numerische Verfahren zur Lösung dieser Art von Probleme.. doch helfent tut dies nicht..
Ich weiss, hier fehlt jeglicher Ansatz meinerseits, aber ich habe auch wirklich keine Ahnung, wie ich hier vorgehen soll... ich wäre sehr froh, könnte doch jemand mir helfen.. :)
Liebe Grüsse, Amaro
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:47 So 02.05.2010 | | Autor: | Arcesius |
| Aufgabe | | Compute [mm] gcd(23\sqrt{2}-15,3\sqrt{2}+23) [/mm] in [mm] \IQ(\sqrt{2}) [/mm] |
Hallo zusammen
Bitte markiert den letzten Beitrag Grün :)
Ich habe nun nachgelesen, wie man den euklidischen Algorithmus auf die Gaussschen Zahlen anwenden würde und habe mal versucht, es auf diese Aufgabe zu übertragen. Ich präsentiere euch meine Schritte:
a = [mm] 23\sqrt{2} [/mm] - 15
b = [mm] 3\sqrt{2} [/mm] + 23
Dann erhalte ich die Quotienten jeweils, indem ich "Realteil" und "Imaginärteil" abrunde. Der Rest ist dann gegeben durch [mm] r_{n} [/mm] = [mm] r_{n-2}-q_{n}r_{n-1}
[/mm]
[mm] q_{1} [/mm] = [mm] \lfloor\frac{a}{b}\rfloor [/mm] = [mm] \sqrt{2}
[/mm]
[mm] q_{2} [/mm] = [mm] \lfloor\frac{b}{r_{1}}\rfloor [/mm] = -2
[mm] q_{3} [/mm] = [mm] \lfloor\frac{r_{1}}{r_{2}}\rfloor [/mm] = 1
[mm] q_{4} [/mm] = [mm] \lfloor\frac{r_{2}}{r_{3}}\rfloor [/mm] = [mm] 4\sqrt{2}-4
[/mm]
[mm] q_{5} [/mm] = [mm] \lfloor\frac{r_{3}}{r_{4}}\rfloor [/mm] = [mm] \sqrt{2}
[/mm]
[mm] r_{1} [/mm] = [mm] a-bq_{1} [/mm] = -21
[mm] r_{2} [/mm] = [mm] b-r_{1}q_{2} [/mm] = [mm] 3\sqrt{2}-19
[/mm]
[mm] r_{3} [/mm] = [mm] r_{1}-r_{2}q_{3} [/mm] = [mm] -2-3\sqrt{2}
[/mm]
[mm] r_{4} [/mm] = [mm] r_{2}-r_{3}q_{4} [/mm] = [mm] -3-\sqrt{2}
[/mm]
[mm] r_{5} [/mm] = [mm] r_{3}-r_{4}q_{5} [/mm] = 0
Somit wäre [mm] gcd(23\sqrt{2}-15,3\sqrt{2}+23) [/mm] = [mm] -3-\sqrt{2} [/mm] in [mm] \IQ(\sqrt{2})
[/mm]
Kann das stimmen?
Grüsse, Amaro
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 03:17 Mo 03.05.2010 | | Autor: | felixf |
Hallo!
> Compute [mm]gcd(23\sqrt{2}-15,3\sqrt{2}+23)[/mm] in [mm]\IQ(\sqrt{2})[/mm]
> Hallo zusammen
>
> Bitte markiert den letzten Beitrag Grün :)
>
>
> Ich habe nun nachgelesen, wie man den euklidischen
> Algorithmus auf die Gaussschen Zahlen anwenden würde und
> habe mal versucht, es auf diese Aufgabe zu übertragen. Ich
> präsentiere euch meine Schritte:
>
>
> a = [mm]23\sqrt{2}[/mm] - 15
> b = [mm]3\sqrt{2}[/mm] + 23
>
> Dann erhalte ich die Quotienten jeweils, indem ich
> "Realteil" und "Imaginärteil" abrunde. Der Rest ist dann
> gegeben durch [mm]r_{n}[/mm] = [mm]r_{n-2}-q_{n}r_{n-1}[/mm]
>
> [mm]q_{1}[/mm] = [mm]\lfloor\frac{a}{b}\rfloor[/mm] = [mm]\sqrt{2}[/mm]
Es ist [mm] $\frac{a}{b} [/mm] = [mm] -\frac{69}{73} [/mm] + [mm] \frac{82}{73} \sqrt{2}$. [/mm] Wenn du abrundest wuerde jedoch [mm] $\sqrt{2} [/mm] - 1$ herauskommen, und nicht [mm] $\sqrt{2}$. [/mm] Du solltest aber lieber richtig runden als abrunden -- was hier jedoch auf's gleiche hinauslaeuft.
Der Rest stimmt damit vermutlich auch nicht.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 03:14 Mo 03.05.2010 | | Autor: | felixf |
Moin Amaro,
> For the following pairs of algebraic integers (a,b) use the
> Euclidean alg. to find d = gcd(a,b), along with an
> expression ra + sb = d, for some algebraic integers r,s in
> the given quadratic number field
>
> a) a = [mm]23\sqrt{2}[/mm] - 15, b = [mm]3\sqrt{2}[/mm] + 23 in
> [mm]\IQ(\sqrt{2})[/mm]
gemeint ist vermutlich den ggT im entsprechenden Ganzheitsring zu bestimmen?
> Ich verzweifle noch.. wir haben den Euclidischen
> algorithmus vor langer Zeit für ganze Zahlen gesehen...
> nun sollen wir den ggT von zwei algebraischen Zahlen in
> [mm]\IQ(\sqrt{d})[/mm] finden..
>
> Ich habe nun lange nach einer Vorgehensweise gesucht, doch
> erfolglos.. das meiste das ich gefunden habe waren
> hauptsächlich Papers über numerische Verfahren zur
> Lösung dieser Art von Probleme.. doch helfent tut dies
> nicht..
>
> Ich weiss, hier fehlt jeglicher Ansatz meinerseits, aber
> ich habe auch wirklich keine Ahnung, wie ich hier vorgehen
> soll... ich wäre sehr froh, könnte doch jemand mir
> helfen.. :)
Du musst dir ueberlegen, wie "Divison mit Rest" in dem Ganzheitsring aussieht. Normalerweise schaust du die Normabbildung (mit Betrag versehen, damit nichts negatives herauskommt) an, nennen wir sie mal $d : [mm] \mathcal{O}_K \to \IN_{\ge 0}$, [/mm] und um $a = q b + r$ zu bestimmen mit $d(r) < d(b)$ schaust du dir [mm] $\frac{a}{b}$ [/mm] an. Du musst jetzt ein $q [mm] \in \mathcal{O}_K$ [/mm] finden, so dass [mm] $d(\frac{a}{b} [/mm] - q) < 1$ ist; daraus folgt, dass $r := a - q b$ gerade $d(r) < d(b)$ erfuellt.
Jetzt musst du dir ueberlegen, wie du aus [mm] $\frac{a}{b}$ [/mm] denn $q$ bestimmst. Ist [mm] $\frac{a}{b} [/mm] = x + y [mm] \sqrt{2}$, [/mm] so kannst du z.B. $x$ und $y$ runden, sagen wir auf $x', y'$, und $q := x' + [mm] \sqrt{2} [/mm] y'$ setzen: dann gilt [mm] $d(\frac{a}{b} [/mm] - q) = |(x - [mm] x')^2 [/mm] - 2 (y - [mm] y')^2|$. [/mm] Wegen $|x - x'|, |y - y'| [mm] \le \frac{1}{2}$ [/mm] folgt dann [mm] $d(\frac{a}{b} [/mm] - q) [mm] \le \frac{1}{2} [/mm] < 1$.
Das passt auch gut zu dem, was du in den Gaussschen Zahlen [mm] $\IZ[i]$ [/mm] gemacht hast, abgesehen dass man auch da nicht abrunden darf, sondern richtig runden muss.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:53 Mo 03.05.2010 | | Autor: | Arcesius |
Hallo Felix
> Moin Amaro,
> Du musst dir ueberlegen, wie "Divison mit Rest" in dem
> Ganzheitsring aussieht. Normalerweise schaust du die
> Normabbildung (mit Betrag versehen, damit nichts negatives
> herauskommt) an, nennen wir sie mal [mm]d : \mathcal{O}_K \to \IN_{\ge 0}[/mm],
> und um [mm]a = q b + r[/mm] zu bestimmen mit [mm]d(r) < d(b)[/mm] schaust du
> dir [mm]\frac{a}{b}[/mm] an. Du musst jetzt ein [mm]q \in \mathcal{O}_K[/mm]
> finden, so dass [mm]d(\frac{a}{b} - q) < 1[/mm] ist; daraus folgt,
> dass [mm]r := a - q b[/mm] gerade [mm]d(r) < d(b)[/mm] erfuellt.
>
> Jetzt musst du dir ueberlegen, wie du aus [mm]\frac{a}{b}[/mm] denn
> [mm]q[/mm] bestimmst. Ist [mm]\frac{a}{b} = x + y \sqrt{2}[/mm], so kannst du
> z.B. [mm]x[/mm] und [mm]y[/mm] runden, sagen wir auf [mm]x', y'[/mm], und [mm]q := x' + \sqrt{2} y'[/mm]
> setzen: dann gilt [mm]d(\frac{a}{b} - q) = |(x - x')^2 - 2 (y - y')^2|[/mm].
> Wegen [mm]|x - x'|, |y - y'| \le \frac{1}{2}[/mm] folgt dann
> [mm]d(\frac{a}{b} - q) \le \frac{1}{2} < 1[/mm].
>
> Das passt auch gut zu dem, was du in den Gaussschen Zahlen
> [mm]\IZ[i][/mm] gemacht hast, abgesehen dass man auch da nicht abrunden [/i][/mm]
> [mm][i]darf, sondern richtig runden muss.[/i][/mm]
Was meinst du eigentlich mit "richtig runden"? Nicht den Real- bzw. Imaginärteil für sich gesehen, sondern die komplexe Zahl selbst?
Sonst wurde mir durch deine Erklärung einiges klarer.. danke dafür!
> [mm][i] [/i][/mm]
> [mm][i]LG Felix[/i][/mm]
> [mm][i] [/i][/mm]
Grüsse, amaro
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:29 Mo 03.05.2010 | | Autor: | felixf |
Hallo Amaro,
> > Das passt auch gut zu dem, was du in den Gaussschen Zahlen
> > [mm]\IZ[i][/mm] gemacht hast, abgesehen dass man auch da nicht [/i][/mm]
> [mm][i]abrunden[/i][/mm]
> > [mm][i]darf, sondern richtig runden muss.[/i][/mm]
>
> Was meinst du eigentlich mit "richtig runden"? Nicht den
> Real- bzw. Imaginärteil für sich gesehen, sondern die
> komplexe Zahl selbst?
Schon Real- und Imaginaerteil fuer sich, ich meinte dass du "richtig" rundest, also zu $x [mm] \in \IR$ [/mm] eine ganze Zahl [mm] $\hat{x} \in \IZ$ [/mm] nimmst mit $|x - [mm] \hat{x}| \le \frac{1}{2}$. [/mm] Und nicht [mm] $\lfloor [/mm] x [mm] \rfloor$ [/mm] oder [mm] $\lceil [/mm] x [mm] \rceil$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:07 Mo 03.05.2010 | | Autor: | Arcesius |
Hallo
Trotzdem doch noch schnell eine Frage...
Je nach dem werde ich eine unendliche Kette erhalten, ohne zu einem Ende zu kommen (ich sitze gerade vor so einem Beispiel..).
Was kann ich daraus schliessen? Kann ich einfach gcd(a,b) = 1 herausfolgern?
Danke schonmal für die Mühe :)
Grüsse, Amaro
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:32 Mo 03.05.2010 | | Autor: | felixf |
Hallo Amaro!
> Je nach dem werde ich eine unendliche Kette erhalten, ohne
> zu einem Ende zu kommen (ich sitze gerade vor so einem
> Beispiel..).
Nunja, fast alle Glieder der Kette muessen dann Einheiten sein.
> Was kann ich daraus schliessen? Kann ich einfach gcd(a,b)
> = 1 herausfolgern?
Guck mal, ob du zufaellig eine Einheit rausbekommst. Dann ist der ggT gleich 1.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:53 Mo 03.05.2010 | | Autor: | Arcesius |
| Aufgabe | | a = [mm] 5\sqrt{7} [/mm] + 17, b = 38 in [mm] \mathbb{Q}(\sqrt{7}) [/mm] |
Bisher habe ich bei meiner Rechnung noch keine Einheit erhalten.. aber ich habe einen Fehler gefunden und bin jetzt zu einem Ende gekommen.
Allerdings bin ich nicht sicher, wegen dem Runden..
Ich bin nun in [mm] \mathbb{Q}(\sqrt{7})
[/mm]
[mm] d(\frac{a}{b} [/mm] - q) ist mit q abgerundet wie vorher und |x-x'|,|y-y'| [mm] \le \frac{1}{2} [/mm] ergibt sich
[mm] d(\frac{a}{b}-q) \le |\frac{1}{4}-7\frac{1}{4}| [/mm] = [mm] \frac{3}{2}
[/mm]
Also muss ich doch je nach dem anders abrunden, oder nicht? also wie du erwähnt hast, "richtig runden".
Jedoch erhalte ich für den ersten Quotienten:
[mm] q_{1} [/mm] = [mm] \lfloor\frac{a}{b}\rfloor [/mm] = 0. Dann ist immernoch [mm] d(\frac{a}{b}-q_{1}) [/mm] < 1
Also kann ich ja so weiter machen.. oder?
Dann erhalte ich gcd(a,b) = [mm] 23+9\sqrt{7}
[/mm]
(Schon der dritte Rest ist 0..)
Danke für eure Geduld!
Grüsse, Amaro
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:06 Di 04.05.2010 | | Autor: | felixf |
Hallo!
> a = [mm]5\sqrt{7}[/mm] + 17, b = 38 in [mm]\mathbb{Q}(\sqrt{7})[/mm]
>
> Bisher habe ich bei meiner Rechnung noch keine Einheit
> erhalten.. aber ich habe einen Fehler gefunden und bin
> jetzt zu einem Ende gekommen.
> Allerdings bin ich nicht sicher, wegen dem Runden..
>
> Ich bin nun in [mm]\mathbb{Q}(\sqrt{7})[/mm]
>
> [mm]d(\frac{a}{b}[/mm] - q) ist mit q abgerundet wie vorher und
> |x-x'|,|y-y'| [mm]\le \frac{1}{2}[/mm] ergibt sich
> [mm]d(\frac{a}{b}-q) \le |\frac{1}{4}-7\frac{1}{4}|[/mm] =
> [mm]\frac{3}{2}[/mm]
Das letzte stimmt nicht! Es gilt [mm] $d(\frac{a}{b} [/mm] - q) [mm] \le \sup_{0 \le a, b \le 1/2} |x^2 [/mm] - 7 [mm] b^2|$. [/mm] Dieses Supremum wird aber nicht fuer $a = b = 1/2$ angenommen, sondern fuer $a = 0$ und $b = 1/2$: dann ist es naemlich $7/4 = 1.725$. Und das ist eindeutig groesser als 1.
Ganz so einfach kannst du hier also nicht vorgehen. Du musst schon $q$ so waehlen, dass [mm] $d(\frac{a}{b} [/mm] - q)$ wirklich kleiner als 1 ist.
LG Felix
|
|
|
|
