ggt bei Gaußschen Zahlen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:37 Mo 04.03.2013 | | Autor: | shnicky |
Hallo zusammen,
ich habe eine Frage zum euklidischen Algorithmus bei Gaußschen Zahlen.
Wir haben den Algorithmus wie folgt gelernt:
Gesucht wird $ [mm] ggT(\alpha,\beta) [/mm] $ mit $ [mm] \alpha [/mm] $ und $ [mm] \beta [/mm] $ aus den gaußschen Zahlen.
Vorgehensweise: Bestimme $ [mm] \alpha/\beta= [/mm] $ u+iv
wir runden u auf die nächstgelegene ganze Zahl m und v auf die nächstgelegene ganze Zahl n.
Sei q=n+mi und $ [mm] r=\alpha-q\beta [/mm] $
Nun fangen wir wieder von vorne an mit $ [mm] \beta [/mm] $ statt $ [mm] \alpha [/mm] $ und r statt $ [mm] \beta. [/mm] $
Meine Frage ist nun wieso wir u und v auf die nächstgelegene Zahl runden und nicht wie im "normalen" euklidischen Algorithmus immer abrunden.
Andererseits steht in unserem Buch (a course in computational number theory), dass es egal ist, ob u und v auf- oder abgerundet werden. Wieso ist das so?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:15 Mo 04.03.2013 | | Autor: | felixf |
Moin!
> ich habe eine Frage zum euklidischen Algorithmus bei
> Gaußschen Zahlen.
> Wir haben den Algorithmus wie folgt gelernt:
> Gesucht wird [mm]ggT(\alpha,\beta)[/mm] mit [mm]\alpha[/mm] und [mm]\beta[/mm] aus
> den gaußschen Zahlen.
> Vorgehensweise: Bestimme [mm]\alpha/\beta=[/mm] u+iv
> wir runden u auf die nächstgelegene ganze Zahl m und v
> auf die nächstgelegene ganze Zahl n.
> Sei q=n+mi und [mm]r=\alpha-q\beta[/mm]
> Nun fangen wir wieder von vorne an mit [mm]\beta[/mm] statt [mm]\alpha[/mm]
> und r statt [mm]\beta.[/mm]
Genau.
> Meine Frage ist nun wieso wir u und v auf die
> nächstgelegene Zahl runden und nicht wie im "normalen"
> euklidischen Algorithmus immer abrunden.
Wieso sollte man im "normalen" euklidischen Algorithmus immer abrunden? Man muss einfach einen Rest nehmen, der betragsmaessig kleiner als der Divisor ist. Ob der Rest nun positiv oder negativ ist, ist voellig egal.
> Andererseits steht in unserem Buch (a course in
> computational number theory), dass es egal ist, ob u und v
> auf- oder abgerundet werden. Wieso ist das so?
Warum sollte es nicht egal sein?
Du brauchst fuer den euklidischen Algorithmus nur, dass die euklidische Bewertung der Reste (meist der Betrag der Reste) eine echt absteigende Folge liefert. Welchen Rest man dafuer nun genau nimmt bzw. welchen Quotienten, ist folglich voellig egal.
Also konkret: ob du nun $6 = 1 [mm] \cdot [/mm] 5 + 1$ oder $6 = 2 [mm] \cdot [/mm] 5 - 4$ schreibst, ist wirklich egal, da $|1|, |-4| < |5|$. Du kommst bei beiden Ansaetzen in endlich vielen Schritten zum ggT.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:39 Mo 04.03.2013 | | Autor: | reverend |
Moin Felix,
ich gestehe, dass ich überhaupt jetzt erst verstehe, was eigentlich gemeint ist. Unter "abrunden" und "aufrunden" habe ich bisher etwas anderes verstanden...
Grüße
reverend
|
|
|
| |
|
Huch, da ist wohl deine Aufgabenstellung verloren gegangen.
Aber kein Problem, ich hab sie dir wiederhergestellt. ;)
Sollte es kein Versehen gewesen sein so lass die Aufgabenstellung bitte demnächst stehen, denn sie nach Beantwortung der Frage zu löschen ist sowohl den Beantwortern als auch anderen an dem Thema interessierten gegenüber sehr unfair.
lg
Schadow
|
|
|
| |
|
moin,
@ reverend: In [mm] $\IZ[i]$ [/mm] ist bei der Berechnung schon das "klassische" Auf- und Abrunden gemeint.
Wenn wir eine Division mit Rest von einem $b [mm] \in \IZ$ [/mm] durch ein $a [mm] \in \IZ$ [/mm] durchführen, bestimmten wir ja $q,r [mm] \in \IZ$ [/mm] so, dass $b=qa+r$ und $|r|<|a|$.
Dies kann man in [mm] $\IZ$ [/mm] meist durch Ausprobieren machen - "Wie oft passt $a$ in $b$?" - in [mm] $\IZ[i]$ [/mm] geht das mangels einer Anordnung des Rings allerdings nicht so schön.
Haben wir jetzt also $a,b [mm] \in \IZ[i]$ [/mm] und wollen $q,r [mm] \in \IZ[i]$ [/mm] bestimmen mit $b = qa+r$ und $|r|<|a|$ (hiermit ist der komplexe Betrag gemeint), so können wir also nicht einfach ausprobieren.
Am Beispiel:
$b = 2+3i$, $a=1+2i$. Wir berechnen als erstes [mm] $\frac{b}{a} [/mm] = [mm] \frac{8}{5} [/mm] - [mm] \frac{1}{5}i \in \IC$. [/mm] Nun runden wir beide Vorfaktoren und erhalten als mögliche Wahlen für unser $q$ (jenachdem wie wir runden):
[mm] $q_1 [/mm] = 1$, [mm] $q_2 [/mm] = 2$, [mm] $q_3 [/mm] = 1-i$, [mm] $q_4 [/mm] = 2-i$.
Schreiben wir nun $b = [mm] q_ia+r_i$ [/mm] mit $i=1,2,3,4$ so erhalten wir
[mm] $r_1 [/mm] = 1+i$
[mm] $r_2 [/mm] = -i$
[mm] $r_3 [/mm] = -1+2i$
[mm] $r_4 [/mm] = 2$
Zuerst sehen wir hier (wenn ich mich nicht verrechnet habe^^), dass das Runden zur jeweils nächsten ganzen Zahl den betragsmäßig kleinsten Rest [mm] ($r_2$) [/mm] liefert.
Dann sehen wir, dass [mm] $q_3$ [/mm] keine geschickte Wahl ist, da [mm] $|r_3|=|a|$.
[/mm]
Das ist natürlich sehr unschön, denn gehen wir jetzt in den nächsten Schritt des Algorithmus, berechnen [mm] $\frac{a}{r_3} [/mm] = [mm] \frac{3}{5} [/mm] - [mm] \frac{4}{5}i$ [/mm] und runden dies ungünstigerweise zu [mm] $\tilde{q} [/mm] = 0$, so laufen wir in eine Endlosschleife.
Es ist also wie an diesem Beispiel zu sehen NICHT egal, wie man rundet, man muss schon immer zur nächsten ganzen Zahl runden oder aber von Hand nachrechnen, dass der Betrag wirklich echt kleiner wird.
lg
Schadow
|
|
|
|
