Gauß'sche Zahlen < Gruppe, Ring, Körper < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Der Ring [mm] \IZ[i] [/mm] der Gauß'schen Zahlen ist euklidisch.
Beweis: Die Elemente des von einem festen von Null verschiedenen Element 0 [mm] \not= [/mm] a=x+iy [mm] \in \IZ[i] [/mm] im Ring [mm] \IZ[i] [/mm] der Gauß'schen Zahlen erzeugten Hauptideals bilden die Ecken eines quadratischen Rasters auf der komplexen Zahlenebene, mit |a|= [mm] \sqrt{x^2+y^2} [/mm] der Seitenlänge der Quadrate. Jedes b [mm] \in \IZ[i] [/mm] liegt in einem dieser Quadrate und hat von einer der Ecken einen Abstand [mm] \le \sqrt{2}|a|/2 [/mm] < |a|. Folglich ist unser Ring euklidisch mit [mm] \sigma(a)=|a|^2. [/mm] |
Hallo!
Hier ist mir eigentlich nur der letzte Satz nicht klar.
Wie kommt man auf dieses [mm] \sigma(a)=|a|^2?
[/mm]
Liebe Grüße,
Lily
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:05 Sa 06.08.2016 | | Autor: | indyze |
Guten Abend, Mathe-Lily! 
Wie man darauf kommt, müssten wir schon Gauß höchstselbst fragen.  Nun, vielleicht kann ich dennoch erklären, weshalb das Ganze funktioniert. Damit [mm] $(\mathds{Z}[i],\sigma)$ [/mm] euklidisch ist, ist die folgende Eigenschaft zu verifizieren:
Zu zeigen: Für [mm] $a,b\in\mathds{Z}[i]$, $a\not=0$ [/mm] gibt es ein [mm] $u\in\mathds{Z}[i]$, [/mm] sodass für $r:=b-au$ gilt: [mm] $|r|^2<|a|^2$.
[/mm]
Wir müssen also die Distanz von $b$ zum nächsten Gitterpunkt $au$ abschätzen. Die geometrischen Überlegungen, welche Du zitiert hast, zeigen, dass der Abstand $|r|$ zum nächsten Gitterpunkt durch [mm] $\sqrt{2}|a|/2$ [/mm] beschränkt ist, also ist [mm] $|r|^2\le|a|^2/2<|a|^2$. [/mm] Damit ist alles gezeigt.
Aufgabe für das Verständnis: Führe eine Division mit Rest durch mit $a=1-21i$ und $b=23+11i$.
Mathematische Grüße
indyze
|
|
|
| |
|
Hallo indyze!!
Vielen Dank für deine Antwort!
> Damit
> [mm](\mathds{Z}[i],\sigma)[/mm] euklidisch ist, ist die folgende Eigenschaft zu verifizieren: Zu zeigen: Für [mm]a,b\in\mathds{Z}[i][/mm], [mm]a\not=0[/mm] gibt es ein [mm]u\in\mathds{Z}[i][/mm], sodass für [mm]r:=b-au[/mm] gilt: [mm]|r|^2<|a|^2[/mm]. Wir müssen also die Distanz von [mm]b[/mm] zum nächsten Gitterpunkt [mm]au[/mm] abschätzen. Die geometrischen Überlegungen, welche Du zitiert hast, zeigen, dass der Abstand [mm]|r|[/mm] zum nächsten Gitterpunkt durch [mm]\sqrt{2}|a|/2[/mm] beschränkt ist, also ist [mm]|r|^2\le|a|^2/2<|a|^2[/mm]. Damit ist alles gezeigt.
Achso! Habe jetzt verstanden, dass in [mm] \IZ[i] \sigma(a)=|a|^2 [/mm] ist, das erklärt für mich den Beweis! Toll, danke!
> Aufgabe für das Verständnis: Führe eine Division mit Rest durch mit [mm]a=1-21i[/mm] und [mm]b=23+11i[/mm].
Hier bin ich aber ins Straucheln geraten: Ich wollte die Division durch den Euklidischen Algorithmus machen, den ich schon mal mit anderen komplexen Zahlen ausprobiert habe, aber hier geht das leider nicht so schön auf und daher mal mein Versuch:
[mm] \bruch{a}{b}= \bruch{1-21i}{23+11i}= \bruch{(1-21i)(23-11i)}{(23+11i)(23-11i)}= \bruch{-208}{650}- \bruch{494}{650}i [/mm]
Bisher dachte ich man müsse nun Real- und Imaginärteil runden auf die nächstgrößere ganze Zahl. Stimmt das? Denn das wäre ja nun in beiden Fällen 0! Dann hätten a und b keinen gemeinsamen Teiler und der Rest wäre =b ?
Liebe Grüße, Lily
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:13 So 07.08.2016 | | Autor: | leduart |
Hallo
du musst wirklich dividieren mit Rest, also euklidischer Alg., von dem du sagst, dass du es kannst. "aufgehen kann es nicht, aber du kannst den Rest bestimmen.
Gruß leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:37 So 07.08.2016 | | Autor: | indyze |
Noch einmal schönen Tag, Mathe-Lily!
Ich kann Dich zunächst beruhigen: Wenn es darum geht, $a$ mit Rest durch $b$ zu dividieren, hast Du alles richtig gemacht. Denn es gilt ja bereits [mm] $|a|^2=1^2+21^2=442<650=23^2+11^2=|b|^2$. [/mm] Also ist [mm] $a=0\cdot [/mm] b+a$ das fertige Ergebnis der Division mit Rest; der Rest ist einfach $a$.
Ich hatte allerdings eigentlich vorgesehen, $b$ durch $a$ zu dividieren, da die Buchstaben so auch in der Fragestellung besetzt waren. Den korrekten Algorithmus hast du ja bereits skizziert; ich formuliere ihn für die Nachwelt noch einmal in Pseudcode:
Algorithmus (Division mit Rest in [mm] $\mathds{Z}[i]$):
[/mm]
Eingabe: [mm] $a,b\in\mathds{Z}[i]$, $a\not=0$.
[/mm]
Ausgabe: [mm] $u,r\in\mathds{Z}[i]$, [/mm] sodass [mm] $b=a\cdot [/mm] u+r$ und $|r|<|a|$.
1) Berechne $z=b/a$ in [mm] $\IC$.
[/mm]
2) Berechne $u$ = die Nächstgelegene Gaußsche Zahl zu $z$.
3) Berechne $r=b-au$.
Noch eine kleine Anmerkung: Um den ggT von $a$ und $b$ zu berechnen, benötigt man noch etwas mehr, als die Division mit Rest, nämlich den eigentlichen euklidischen Algorithmus. Insofern hast Du oben falsch geschlossen, dass $a$ und $b$ keinen ggT hätten, denn da [mm] $\mathds{Z}[i]$ [/mm] ja bewiesenermaßen euklidisch und damit ein Hauptidealbereich ist, existiert ein ggT immer. Ich schlage vor, dass Du auch den euklidischen Algorithmus einmal zur Berechnung des ggT von $1-21i$ und $23+11i$ durchführst - die Division mit Rest ist ja der erste Schritt dazu.
Aufgabe für das algorithmische Denken: Schreibe einen Algorithmus, der das Folgende leistet und beweise, dass er korrekt ist:
Algorithmus (Euklidischer Algorithmus in [mm] $(R,\sigma)$):
[/mm]
Eingabe: [mm] $a,b\in [/mm] R$.
Ausgabe: [mm] $d,x,y\in [/mm] R$, sodass [mm] $d=\ggT(a,b)$, [/mm] $d=xa+yb$.
Mathematische Grüße
indyze
|
|
|
| |
|
Hallo!
Vielen Dank für deine ausführliche Antwort!
Ich habe den Euklidischen Algorithmus durchgeführt und erhalten:
ggT(a,b)=-5+i
Und zum Algorithmus:
n=0: [mm] a_0:=a \Rightarrow [/mm] Sei [mm] d_0=1, e_0=0
[/mm]
n=1: [mm] a_1:=b \Rightarrow [/mm] Sei [mm] d_1=0, e_1=1
[/mm]
n [mm] \ge [/mm] 2:
- [mm] a_{n-1}=0 \Rightarrow [/mm] Setze N=n-1 und brich ab
- [mm] a_{n-1} \not= [/mm] 0 [mm] \Rightarrow [/mm] Dividiere [mm] \bruch{a_{n-2}}{a_{n-1}} [/mm] mit Rest in R [mm] \Rightarrow a_{n-2}=q_n a_{n-1}+ r_n [/mm] mit [mm] q_n, r_n \in [/mm] R
Dann setze [mm] a_n:= r_n, d_n [/mm] := [mm] d_{n-2} [/mm] - [mm] q_n d_{n-1}, e_n [/mm] := [mm] e_{n-2} [/mm] - [mm] q_n e_{n-1}
[/mm]
Dann gilt für alle n=0,...,N: [mm] a_n [/mm] = [mm] d_n a_0 [/mm] + [mm] e_n a_1
[/mm]
und [mm] ggT(a_0,a_1)=a_{N-1}
[/mm]
Den erste Teil kann man einfach durch vollständige Induktion beweisen: n=0 klar wegen gesetzten Werten; wenn die Gleichung für alle Werte bis einschließlich n gilt, ist sie für n+1 durch Einsetzen und Umstellen schnell bewiesen.
Aber beim zweiten Teil: mir ist klar, warum es gilt:
[mm] a_N=r_N=0
[/mm]
und: der ggT zwei aufeinanderfolgender [mm] a_k [/mm] ist immer gleich also auch: [mm] ggT(a_0,a_1)=ggT(a_{N-1},a_N)=ggT(a_{N-1},0) [/mm]
und: [mm] a_{N-1} \in ggT(a_{N-1},0)
[/mm]
Aber reicht das so?
Liebe Grüße, Lily
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:41 Mo 08.08.2016 | | Autor: | indyze |
Guten Morgen, Mathe-Lily!
Der Algorithmus sieht gut aus! Wenn ich bei ![[]](/images/popup.gif) www.wolframalpha.com den "Code" gcd(1-21i,23+11i) eingebe, erhalte ich $1+5i$ als Ergebnis. Kannst du erklären, woran das liegt?
Auch das Ende sieht sehr gut aus! Wenn $b=au+r$ gilt, so gilt [mm] $b=r\mod\langle a\rangle$ [/mm] - das ist ja der ganze Grund, weshalb man am an der Division mit Rest interessiert ist. Sie erlaubt es einem, eine Normalform von Elementen modulo [mm] $\langle a\rangle$ [/mm] zu berechnen. Hieraus folgt dann, dass [mm] $\langle b,a\rangle=\langle a,r\rangle$. [/mm] Schließlich gilt also den ganzen Algorithmus über [mm] $\langle a_0,a_1\rangle=\dots=\langle a_{N-1},a_N\rangle=\langle a_{N-1}\rangle$. [/mm] In allgemeinen Ringen folgt aus [mm] $\langle a,b\rangle=\langle d\rangle$, [/mm] dass $d$ ein ggT von $a$ und $b$ ist.
In Hauptidealbereichen gilt auch die Umkehrung: $d$ ist genau dann ein ggT, wenn $d$ ein Erzeuger von [mm] $\langle a,b\rangle$ [/mm] ist. Dies ist die Aussage von Bézouts Lemma. In allgemeinen Hauptidealbereichen haben wir aber keine Möglichkeit, eine Linearkombination $d=xa+yb$ algorithmisch zu berechnen. Das tolle an euklidischen Ringen ist, dass es hier eben doch funktioniert.
Aufgabe für das Verständnis: Gib einen Ring $R$ an und zwei Elemente $a,b$, welche einen ggT $d$ besitzen, der allerdings nicht als Linearkombination von $a$ und $b$ geschrieben werden kann. Man kann $R$ sogar faktoriell wählen.
Mathematische Grüße
indyze
|
|
|
| |
|
Guten Morgen, indyze!
>
> Aufgabe für das Verständnis: Gib einen Ring [mm]R[/mm] an und zwei
> Elemente [mm]a,b[/mm], welche einen ggT [mm]d[/mm] besitzen, der allerdings
> nicht als Linearkombination von [mm]a[/mm] und [mm]b[/mm] geschrieben werden
> kann. Man kann [mm]R[/mm] sogar faktoriell wählen.
>
Ich verstehe zwar, was du meinst und es ist mir auch klar, dass man einen faktoriellen Ring oder auch einen Hauptidealring nehmen sollte, aber ich habe gar keine Ansatzpunkt. Wie geht man an so was ran?
Liebe Grüße,
Lily
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:05 Mo 08.08.2016 | | Autor: | indyze |
Noch einmal Hallo!
Ich wäre mir da nicht so sicher, ob Du dich verrechnet hast. Denn zumindest dein Ergebnis ist goldrichtig. Worauf ich nämlich eigentlich hinauswollte, ist, dass der ggT nur bis auf Assoziiertheit (das heißt, bis auf Multiplikation mit einer Einheit) eindeutig bestimmt ist. Und das Ergebnis von wolframalpha unterscheidet sich von deinem Ergebnis genau um den Faktor $i$, also eine Einheit in [mm] $\mathds{Z}[i]$. [/mm] Passt also alles!
Zu der anderen Frage: Man kann hier zum Beispiel $R=k[X,Y]$ wählen, wobei $k$ ein Körper ist. Dann ist jeder gemeinsame Teiler von $X$ und $Y$ konstant. Folglich ist $1$ ein ggT von $X$ und $Y$, aber $1$ lässt sich nicht als Linearkombination von $X$ und $Y$ schreiben.
Ich hoffe, Du hast nun alles gut verstanden, denn diese Dinge sind sehr grundlegend und wichtig, und gleichzeitig auch sehr schön.
Mathematische Grüße
indyze
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:40 So 14.08.2016 | | Autor: | Mathe-Lily |
Vielen Dank, indyze, für die Geduld und die guten Tips und Aufgaben!
Das hat mir sehr geholfen!
Liebe Grüße, Lily
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:09 Mo 08.08.2016 | | Autor: | Mathe-Lily |
Ach, und wegen meinem Ergebnis für den ggT: hab mich zwischendurch verrechnet ^^
|
|
|
|
