ggt für Gaußsche Zahlen

24.01.2012, 09:44

Quad84

Auf diesen Beitrag antworten »

ggt für Gaußsche Zahlen

Guten morgen,

Ich soll mit dem erweiterten eukldischen Alg. den ggt von a und b finden, sowie Elemenete u,v mit u*a+v*b = ggt. Die Zahlen sind:

a = 112 - 14i
b = 51 - 57i

Wie ich den ggt bestimme, weiß ich. Für diesen habe ich 1+i raus.
Wie komme ich aber nun an die 2 fehlenden Elemente?

24.01.2012, 13:20

ollie3

Auf diesen Beitrag antworten »

RE: ggt für Gaußsche Zahlen
hallo quad,
ja das ist ja dann ganz einfach, wenn du den ggt schon hast, setzt du dann
u*a+ v*b= 1+i , die werte für a und b hast du ja, und 2 komplexe zahlen sind
ja dann gleich, wenn realteil und imaginärteil übereinstimmen, das heisst der
realteil von u*a + v*b=1 der imaginärteil davon ebenfalls gleich 1, dann erhälst
du ein lineares gleichungssystem in u und v, und das ist ja einfach zu lösen.
gruss ollie3

24.01.2012, 15:45

galoisseinbruder

Auf diesen Beitrag antworten »

@ollie3:
Da u,v wohl ganze gaußsche Zahlen sein sollen und nicht reell ergibt das 2 Gleichungen für 4 Unbekannte.

@quad84:
wie du schon schreibst: mit dem erweiterten euklidischen Algorithmus.
Wo ist das Problem?

24.01.2012, 16:10

Quad84

Auf diesen Beitrag antworten »

Mein Problem ist, dass ich nicht genau weiß, wie ich den hier anwenden soll. Ich habe den Alg bislang mit einem "Schema" durchgeführt und für die Gaußschen Zahlen kann ich dieses irgendwie nicht anwenden... Könntet ihr mir vlt den 1. Schritt zeigen?

24.01.2012, 16:16

galoisseinbruder

Auf diesen Beitrag antworten »

Da ich dein "Schema" nicht kenne kann ich dir auch nicht den 1.Schritt vorführen.
Allerdings dürfte es für ganze gaußsche zahlen genauso funktionieren wie für ganze Zahlen.
(u,v sollen am Schluß ja wohl ganze gaußsche Zahlen sind.)

24.01.2012, 16:18

Quad84

Auf diesen Beitrag antworten »

ok, ich probiere es mal und poste es dann gleich hier...

Anzeige

24.01.2012, 16:31

Quad84

Auf diesen Beitrag antworten »

Mein "Schema" sieht folgendermaßen aus:

a b q u v

112-14i 51-57i

51-57i 4-8i

4-8i 3-i

3-i 1-i 1 ?

1-i 1+i 0 1

1+i 0 1 0

Ich müsste nun eigentlich rückwärts einsetzen, um auf und v zu kommen. Nur leider komme ich bei den ? nicht mehr weiter....

24.01.2012, 16:34

Quad84

Auf diesen Beitrag antworten »

hm, kann man ja gar nicht lesen ^^
aber ich glaube ich habe gerade den dreh raus ;-)

24.01.2012, 17:00

Quad84

Auf diesen Beitrag antworten »

also ich habe nun lauter brüche raus. das kann also nicht sein, denn VOR ist ja, dass die elemente aus dem ring der gaußschen zahlen sein müssen.

wo liegt denn mein fehler?

24.01.2012, 17:03

galoisseinbruder

Auf diesen Beitrag antworten »

Meine Glaskugel ist grade beim Polieren. Wenn du die Rechnung hier nicht postest kanns dir keiner verraten.

24.01.2012, 17:16

Quad84

Auf diesen Beitrag antworten »

ok, hier nochmal neu:

24.01.2012, 17:20

Quad84

Auf diesen Beitrag antworten »

$\begin{eqnarray*} a = 112 - 14 i<br /> b = 51 - 57 i<br /> Rest: 4 - 8i<br /> <br /> a = 51 - 57i<br /> b = 4 - 8i<br /> Rest: 3 - i<br /> <br /> a = 4 - 8i<br /> b = 3 - i<br /> Rest: 1-i<br /> <br /> a = 3-i<br /> b = 1-i<br /> Rest: 1+i<br /> <br /> a = 1-i<br /> b= 1+i<br /> Rest: 0 \end{eqnarray*}$

24.01.2012, 17:21

Quad84

Auf diesen Beitrag antworten »

Nun muss ja, weil der ggt = 1+i ist, in jeder Zeile gelten:

$\begin{eqnarray*} 1+i = u*a + v*b \end{eqnarray*}$

24.01.2012, 17:23

Quad84

Auf diesen Beitrag antworten »

Dann ergibt sich für die ersten 4 Zeilen (von unten):

$\begin{eqnarray*} u = 1<br /> v = 0<br /> <br /> u = 0<br /> v = 1<br /> <br /> u = 1<br /> v = -2<br /> <br /> u = -2<br /> v = ? \end{eqnarray*}$

Verstehst du, was ich meine?

24.01.2012, 17:28

galoisseinbruder

Auf diesen Beitrag antworten »

Wie kommst du auf den ersten Rest?

24.01.2012, 17:32

Quad84

Auf diesen Beitrag antworten »

Ich habe im 1. Schritt $\begin{eqnarray*} \frac{a}{b} \end{eqnarray*}$ gerechnet.
Da bekomm ich $\begin{eqnarray*} \frac{217}{195} + \frac{189i}{195} \end{eqnarray*}$ raus.

Dann wählt man ja ein Element d, welches am nächsten an diesem Ergebnis liegt. Hier habe ich also d = 1 + i gewählt.

Dann in die Formel:

Rest = a - d*b

einsetzen. Ergibt dann 4 - 8i bei mir.

24.01.2012, 17:41

galoisseinbruder

Auf diesen Beitrag antworten »

Gut. Dann formulier mal deinen dritten Schritt aus.

24.01.2012, 17:46

Quad84

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \frac{4-8i}{3-i} = \frac{(4-8i)*(3+i)}{10} = \frac{20}{10}- \frac{20i}{10} = 2 - 2i = 1-i \end{eqnarray*}$

Dann wähle ich als Element d = 1-i

Und bekomme für den Rest raus:
$\begin{eqnarray*} (4-8i) - (1-i)(3-i)<br /> = 2 - 4i<br /> = 1 - 2i \end{eqnarray*}$

Ok, da hab ich schon nen 1. Fehler gefunden in der obigen Rechnung! Da hab ich nämlich 1 - i geschrieben!

24.01.2012, 17:51

galoisseinbruder

Auf diesen Beitrag antworten »

Was soll die letzte Gleichheit?

Ein bisschen mitdenken beim ausführen von Algorithmen ist hilfreich.
Da

Zitat:

$\begin{eqnarray*} \frac{4-8i}{3-i} = \frac{(4-8i)*(3+i)}{10} = \frac{20}{10}- \frac{20i}{10} = 2 - 2i \end{eqnarray*}$

ist
$\begin{eqnarray*} 4-8i =(2-2i)(3-i) \end{eqnarray*}$
kein rest.

24.01.2012, 17:55

Quad84

Auf diesen Beitrag antworten »

also ist der ggt von den anfänglichen elementen 2 - 2i.

und kann ich dann einfach rückwärts einsetzen, so wie bei ganzen zahlen, und die elemente u und v bestimmen? also so, wie ich es - wenn auch falsch - gemacht habe?

24.01.2012, 18:06

galoisseinbruder

Auf diesen Beitrag antworten »

Nein. Der ggT ist 3-i.

Und das der erweiterte Euklid ict nichts anderes als rüchwärts einsetzen.

Im Übrigen ist es manchmal hilfreich folgende Probe zu machen.
Ist $\begin{eqnarray*} N(a+ib)=a^2+b^2 \end{eqnarray*}$ die Funktion die die ganzen Gaußschen zahlen zu einem euklidischen Ring machen so gilt: ( $\begin{eqnarray*} x,y \in \mathbb Z[i] \end{eqnarray*}$ )
$\begin{eqnarray*} N(ggT(x,y)) | N(x),N(y) \end{eqnarray*}$
und damit sogar
$\begin{eqnarray*} N(ggT(x,y)) | ggT(N(x),N(y)) \end{eqnarray*}$
was deine beiden vorgeschlagenen Kandidaten nicht erfüllt haben.

24.01.2012, 18:09

Quad84

Auf diesen Beitrag antworten »

VIELEN DANK FÜR DEINE HINWEISE!!!! Freude

Freude

Ich werde es gleich ausprobieren!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »