ggT bei gaußschen ganzen Zahlen

[noRkia]

mein problemthema

hier

http://de.wikiversity.org/wiki/Kateg...it_L%C3%B6sung

finden sich ja 2 beispiele.

diese sind auch klar,weil als approximation immer eine ganze zahl,also eine gaußsche ganze zahl mit b = 0 gewählt wird.
es gibt doch auch fälle bei denen es eine zahl mit b |= 0 sein kann.
wenn ich es mit eigenen zahlen ausprobiere mache ich 10 approximationen und es hört nicht auf ;/

gibt es dafür irgendwo einen rechner?

[Brauni90]

Wenn du noch etwas präziser sein kannst und einen C++-Compiler besitzt, könnte ich ein paar Zeilen basteln.
Sicherlich meinst du keinen Rechner für eine Division, sondern vielmehr einen für den ggT zweier komplexer Zahlen?

[noRkia]

also bei den gaußschen ganzen zahlen Z[i] sind genau die komplexen zahlen (a+bi) gemeint bei denen a und b ganze zahlen sind.

diese menge ist ein euklidscher ring und deshalb gibt es einen euklidschen algoritmus der den ggt bestimmt.

problem:da die komplexen zahlen und damit auch Z[i] nicht anordbar sind,das heisst es gibt reihen folge und man kann nicht sagen eine zahl ist grösser als eine andere muss man eben zuerst wie in dem wikibeispiel eine multiplikation mit 1 =(c-di)/(c-di) durchführen damit im nenner nur noch eine ganze zahl steht.nun wird eine zahl aus Z[i] gesucht die diese am besten annähert.

dauu betrachet man einfach die einzelnen brüche a/(c+di)*(c-di)
und b/(c+di)*(c-di) (wobei natürlich (c+di)*(c-di) = c²+d² ist) und rundet dann entsprechend ab.sagen wir (e+fi) nähert am besten an.

dann ist (a+bi) = (e+fi)*(c+di) + rest

danach wird wie sonst auch geschaut wie oft der rest in c+di passt und das ganze wiederholt sich bei man bei einer einheit oder ganzen zahl angekommen ist.

was mich nun daran verwirrt ist das das f von (e+fi) in den beispielen immer gleich 0 ist.damit ist e+fi also nur eine ganze zahl.wäre es eine zahl aus Z[i]
dann íst (e+fi)*(c+di) meistens so weit daneben das der rest sehr gross ist und es nicht so aussieht als ob mit dieser algorithmus überhaupt mal ein ergebnis liefert.

man kann auch leider nicht ohne weiteres sein ergebnis überprüfen wenn man selbst zahlen nimmt.warum?

seien a und b gegeben (allgemein) zusätzlich ein c
dann ist ggt(a*c,b*c) = c genau wenn ggt(a,b) = 1


das weis ich ja aber eben vorher nicht ;/

hab keinen c++ compiler,aber es gibt doch sicher genug freeware und downloadmöglichkeiten.

[Brauni90]

Mir ist die Vorgehensweise eigentlich schon klar. Allerdings weiß ich immer noch nicht, ob du einen Rechner zur Überprüfung von ggT(a+ib, c+id) = e+if oder einen Rechner zur Anzeige der schrittweisen Vorgehensweise mit (selbstgewählter?) bester Approximation willst.

,aber es gibt doch sicher genug freeware und downloadmöglichkeiten.

...

Vermutlich, aber kommt drauf an, welchen Rechner du benötigst (s.o.), wobei ich persönlich ein kompaktes, in C++ geschriebenes Programm dennoch bevorzugen würde.

[noRkia]

ich suche einfach ein programm das denn ggt zweier zahlen ausgibt.
ohne rechenweg.

[Brauni90]

Ein Programm hätte ich, aber ohne Compiler bringt es dir nicht viel. Allerdings könnte ich dir das native Konsolenprogramm zukommen lassen, wenn du das Risiko eingehen willst.

Solltest du dennoch auf einen leicht zu erkennenden Fehler stoßen, die relevanten Daten kurz notieren.

[noRkia]

wäre sehr nett.
schreib mir einfach wie ich es benutzen muss und was ich mir dazu runterladen muss ^ ^

[Brauni90]

Hast du sie erhalten?