ggT (... und in nicht-Euklidischen Ringen?)

29/12/2010 - 17:28 von Martina Eckner | Report spam
Hallo zusammen,

mir ist wieder mal eine in meinen Augen interessante Frage über den Weg
gelaufen:

(Wer will, kann sich den Teil mit den natürlichen Zahlen ersparen.)

************************************************

Zu zeigen ist für alle natürlichen Zahlen a, b, n:

ggT(n*a,n*b) = n*ggT(a,b)

Vielleicht sollte sinnvollerweise n ungleich 0 sein, aber vielleicht
fàngt in dieser Vorlesung (Mathe auf Lehramt) |N sowieso erst bei 1 an ...

OK, ich weiß nicht, wie die Musterlösung aussieht. Ich würde es mit dem
Euklidischen Algorithmus machen:

Wenn man den ggT(a,b) bestimmt, macht man das ja mit dem Euklidischen
Algorithmus und hat mit dem Anfang a_0 = a und a_1 = b immer die Zeilen

a_i = c{i+1} * a_{i+1} + a_{i+2}

wobei a_{i+2} < a_{i+1} sein muß und dadurch c{i+1} und a_{i+2}
eindeutig bestimmt sind. Wenn schließlich a_{k+2}=0 ist, ist a_{k+1}
genau der ggT(a,b).

Wenn man den Euklidischen Algorithmus dann für den ggT(na,nb)
hinschreibt, sieht man, daß man an der Stelle i die Zeile

n*a_i = c{i+1} * n*a_{i+1} + n*a_{i+2}

hat, dann ist irgendwann n*a_{k+2}=0, und n*a_{k+1} ist der ggT(na,nb),
aber n*a_{k+1} ist ja genau n*ggT(a,b).

Gut, aber das ist ja sicherlich ein bißchen aufwendig, das
vernünftig-korrekt aufzuschreiben. Außerdem hat man dafür verwendet, daß
es sich um einen Euklidischen Ring handelt.

Eine andere Möglichkeit wàre:

Es gibt natürliche Zahlen k, l, k' und l' mit

ggT(a,b) * k = a und ggT(a,b) * l = b und
ggT(na,nb) * k' = na und ggT (na,nb) * l' = nb

wobei k und l beziehungsweise k' und l' teilerfremd sind, und damit gilt
wegen
k/l = a/b = (na)/(nb) = k'/l'
daß k=k' und l=l' ist, und daraus folgt dann die Behauptung.

Hier braucht man aber als Voraussetzung, daß der Ring faktoriell ist
(oder etwa nicht?)

************************************************

Nun zu meiner eigentlichen Frage:

"Kann man den ggT auch in nicht-Euklidischen oder sogar
nicht-faktoriellen Ringen vernünftig defineren? Gilt dann auch
ggT(na,nb) = n*ggT(a,b)?"

Ich habe in dem Skript nàmlich noch eine weitere Charakterisierung des
ggT gesehen:

x=ggT(a,b) genau dann, wenn für alle natürlichen Zahlen t gilt:
Wenn t|a und t|b, dann t|x.

Klar, wenn man den ggT für Ringe so definiert, ist der nur bis auf
Einheiten eindeutig. Aber ist das für allgemeine Ringe überhaupt eine
sinnvolle Definition?

Die Charakterisierung ausnutzend konnte ich n*ggT(a,b)|ggT(na,nb) zeigen:

ggT(a,b)|a und ggT(a,b)|b, daraus folgt:
n*ggT(a,b)|na und n*ggT(a,b)|nb, daraus folgt:
n*ggT(a,b)|ggT(na,nb)

Das war gar nicht so schwer, aber die andere Richtung
ggT(na,nb)|n*ggT(a,b) bekomme ich nicht hin.

Wie gesagt, ich weiß gar nicht, ob der ggT für allgemeine Ringe (ok,
kommutativ mit 1 sollten sie schon sein!) überhaupt funktioniert.
Vielleicht kann mir jemand auch ein schönes Gegenbeispiel nennen.

Viele Grüße!
Martina
 

Lesen sie die antworten

#1 Detlef Müller
30/12/2010 - 13:07 | Warnen spam
Martina Eckner schrieb:
Hallo zusammen,

mir ist wieder mal eine in meinen Augen interessante Frage über den Weg
gelaufen:

(Wer will, kann sich den Teil mit den natürlichen Zahlen ersparen.)

************************************************

Zu zeigen ist für alle natürlichen Zahlen a, b, n:

ggT(n*a,n*b) = n*ggT(a,b)

Vielleicht sollte sinnvollerweise n ungleich 0 sein, aber vielleicht
fàngt in dieser Vorlesung (Mathe auf Lehramt) |N sowieso erst bei 1 an ...

OK, ich weiß nicht, wie die Musterlösung aussieht. Ich würde es mit dem
Euklidischen Algorithmus machen:
...
a_i = c{i+1} * a_{i+1} + a_{i+2}
...

n*a_i = c{i+1} * n*a_{i+1} + n*a_{i+2}

hat, dann ist irgendwann n*a_{k+2}=0, und n*a_{k+1} ist der ggT(na,nb),
aber n*a_{k+1} ist ja genau n*ggT(a,b).

Gut, aber das ist ja sicherlich ein bißchen aufwendig, das
vernünftig-korrekt aufzuschreiben. Außerdem hat man dafür verwendet, daß
es sich um einen Euklidischen Ring handelt.



Ist aber ok - auch über die eindeutige Primfaktorzerlegung
könnte man argumentieren.

Eine andere Möglichkeit wàre:

Es gibt natürliche Zahlen k, l, k' und l' mit

ggT(a,b) * k = a und ggT(a,b) * l = b und
ggT(na,nb) * k' = na und ggT (na,nb) * l' = nb


wobei k und l beziehungsweise k' und l' teilerfremd sind, und damit gilt
wegen
k/l = a/b = (na)/(nb) = k'/l'
daß k=k' und l=l' ist, und daraus folgt dann die Behauptung.

Hier braucht man aber als Voraussetzung, daß der Ring faktoriell ist
(oder etwa nicht?)



Das ist schwàcher als "euklidisch", denn euklidische Ringe sind
automatisch faktoriell (nicht umgekehrt aber man muss sich für
ein Gegenbeispiel etwas anstrengen).

************************************************

Nun zu meiner eigentlichen Frage:

"Kann man den ggT auch in nicht-Euklidischen oder sogar
nicht-faktoriellen Ringen vernünftig defineren? Gilt dann auch
ggT(na,nb) = n*ggT(a,b)?"



Allgemein ist ggT(a,b) in einem Ring R so definiert:
Ein d aus R ist ggT(a,b), wenn gelten

1. d|a und d|b (sprich: d teilt a und d teilt b)

2. für jedes d' aus R mit d'|a und d'|b folgt automatisch
d'|d.

Das "kleiner" aus den Natürlichen Zahlen wird also durch die
Relation "teilt" ersetzt.

Diese Definition ist nicht mehr eindeutig:
der ggT(a,b) ist eigentlich eine Menge von Zahlen die den
Bedingungen 1. und 2. genügen ... es kann sogar sein, daß
diese Menge leer ist.
In den Ganzen Zahlen wàre damit ggT(12, 18) = {-6, 6},
allgemein ist gilt:
d in ggT(a,b), e aus R invertierbar => d*e in ggT(a,b).
Aber das erwàhnst Du ja unten auch noch.

Ich habe in dem Skript nàmlich noch eine weitere Charakterisierung des
ggT gesehen:

x=ggT(a,b) genau dann, wenn für alle natürlichen Zahlen t gilt:
Wenn t|a und t|b, dann t|x.



Mh - wahrscheinlich steht da auch noch die Einschrànkung
x|a und x|b.

Klar, wenn man den ggT für Ringe so definiert, ist der nur bis auf
Einheiten eindeutig. Aber ist das für allgemeine Ringe überhaupt eine
sinnvolle Definition?



Warum nicht?
Die Definition braucht nur eine sinnvolle Definition von "|".

Die Charakterisierung ausnutzend konnte ich n*ggT(a,b)|ggT(na,nb) zeigen:

ggT(a,b)|a und ggT(a,b)|b, daraus folgt:


Es gibt a', b' mit
a = a'*ggT(a,b), b=b'*ggT(a,b) =>
n*a = na'*ggT(a,b), nb=nb'*ggT(a,b) =>
n*a = a'(n*ggT(a,b)), nb=b'*(n*ggT(a,b)) =>
n*ggT(a,b)|na und n*ggT(a,b)|nb, daraus folgt:
n*ggT(a,b)|ggT(na,nb)

Das war gar nicht so schwer, aber die andere Richtung
ggT(na,nb)|n*ggT(a,b) bekomme ich nicht hin.



Vielleicht braucht man hier auch noch weitere Voraussetzungen
an den Ring.

Nehmen wir z.B. den Ring R=Q[X^2,X^3] der Polynome ohne lineares
Glied, also Polynome der Gestalt
a_0 + a_2*X^2 + ... + a_n*X^n, a_i rationale Zahlen.

Die Elemente X^4 und X^5 haben als (bis auf Einheiten) einzigen
gemeinsamen Teiler nur X^2.
Also existiert ggT(X^4,X^5) und ist eben X^2.

Die Elemente

X^2*X^4 = X^6 und X^2*X^5 = X^7

aber haben keinen ggT, denn die gemeinsamen Teiler sind

X^2, X^3, X^4, (beachte: X^5 ist kein Teiler von X^6)
und X^2 teilt X^3 nicht, X^3 teilt X^4 nicht,
X^4 teilt weder X^2 noch X^3.

In R existiert also ggT[X^2*X^4,X^2*X^5] gar nicht und ist
insbesondere nicht X^2*ggT(X^4,X^5)=X^4.

Wie gesagt, ich weiß gar nicht, ob der ggT für allgemeine Ringe (ok,
kommutativ mit 1 sollten sie schon sein!) überhaupt funktioniert.
Vielleicht kann mir jemand auch ein schönes Gegenbeispiel nennen.



Ich hoffe, das gezeigte ist ok.

Gruß,
Detlef
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de

Ähnliche fragen