Größter gemeinsamer Teiler (Ele. Zahlentheorie)

09.11.2017, 10:56

Opher19782808

Größter gemeinsamer Teiler (Ele. Zahlentheorie)

Meine Frage:
a) ZZ: ggT(a*b,n)|ggT(a,n) * ggT (b,n)
b) Wann gilt: ggT(a*b,n) = ggT(a,n) * ggT(b,n)

Meine Ideen:
zu a)
Wird der Beweis anhand einer Fallunterscheidung geführt, sprich falls
a|n und b|n klar.
Teilt a|n aber b nicht n ...

zu b)
Wenn a,b teilerfremd und a|n und b|n.
Ist das richtig und abschließend?

09.11.2017, 11:57

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Opher19782808
Ist das richtig und abschließend?

Ganz und gar nicht: Betrachte mal $\begin{align*} a=18,b=12,n=27 \end{align*}$ . Big Laugh

Keine einzige deiner genannten Bedingungen ist erfüllt, und dennoch gilt

ggT(18,27) * ggT(12,27) = 9 * 3 = 27 = ggT(216,27) = ggT(18*12,27) .

Ich würde die Sache auf die Primfaktorebene verlagern:

Primfaktor $\begin{align*} p \end{align*}$ sei in $\begin{align*} a \end{align*}$ mit Exponent $\begin{align*} u \end{align*}$ , in $\begin{align*} b \end{align*}$ mit Exponent $\begin{align*} v \end{align*}$ und in $\begin{align*} n \end{align*}$ mit Exponent $\begin{align*} w \end{align*}$ vertreten. Zu beweisen ist dann

$\begin{align*} \min(u+v,w) \leq \min(u,w)+\min(v,w)\qquad (*) \end{align*}$ .

Jetzt kann man verschiedene Fälle hinsichtlich der Lage von $\begin{align*} w \end{align*}$ bezogen auf $\begin{align*} u,v \end{align*}$ diskutieren (o.B.d.A. dürfen wir $\begin{align*} u\leq v \end{align*}$ annehmen), und in jedem Fall auch das Augenmerk auf Gleichheit in (*) legen...

09.11.2017, 21:26

Opher19782808

Auf diesen Beitrag antworten »

Vielen Dank, aber ich meinte nur ob daran die Fälle unterschieden werden können und habe auf den konkreten Inhalt der Aussage nicht geachtet.
Die Fälle müssen also anhand von Primfaktoren unterschieden werden, habe ich das richtig verstanden?
u<=v kann man annehmen, weil das Problem symmetrisch in der Hinsicht ist, richtig?

Vielen Dank, ist b wenigstens ok?

09.11.2017, 22:05

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Opher19782808
Vielen Dank, ist b wenigstens ok?

Hast du denn nicht gemerkt, dass mein "Ganz und gar nicht" und das folgende Beispiel die Antwort zu deinem b) war? Finger1

Die Anmerkung zum Beispiel

Zitat:

Original von HAL 9000
Keine einzige deiner genannten Bedingungen ist erfüllt

bezieht sich auf deine angeführten (vermuteten?) Bedingungen für Gleichheit

Zitat:

Original von Opher19782808
Wenn a,b teilerfremd und a|n und b|n.

10.11.2017, 11:13

Opher19782808

Auf diesen Beitrag antworten »

Aber das zitierte bezieht sich auf die ganze Aufgabe, sprich a und b.
Als Gegenbeispiel zu b) 18 wie 12 teilt ja nicht 27, was Teil meiner diesbzgl. Bedingung ist.
Vielen Dank erstmal für die Hinweise.
(Ich hoffe ich schreibe es immer mathematisch korrekt und das könnte unbedingt mein Fehler sein, aber das hatte ich gemeint.)

10.11.2017, 11:43

HAL 9000

Auf diesen Beitrag antworten »

Kommen wir zurück zum Beweis: Man muss also im Prinzip nur (*) für beliebige nichtnegative ganze Zahlen $\begin{align*} u,v,w \end{align*}$ nachweisen.

Zitat:

Original von Opher19782808
u<=v kann man annehmen, weil das Problem symmetrisch in der Hinsicht ist, richtig?

Genauer gesagt ist es die Symmetrie bzgl. $\begin{align*} a,b \end{align*}$ , auf der dieses o.B.d.A. beruht, ja.

Man kann nun z.B. bei gegebenen $\begin{align*} u,v \end{align*}$ mit $\begin{align*} u\leq v \end{align*}$ folgende Fallunterscheidung hinsichtlich $\begin{align*} w \end{align*}$ anstellen:

1.Fall: $\begin{align*} w\leq u \end{align*}$

Hier ist $\begin{align*} \min(u+v,w)=\min(u,w)=\min(v,w)=w \end{align*}$ , die Behauptung lautet damit dann $\begin{align*} w\leq 2w \end{align*}$ , was trivialerweise erfüllt ist. Gleichheit tritt genau dann ein, wenn $\begin{align*} w=0 \end{align*}$ ist.

2.Fall: $\begin{align*} u<w<v \end{align*}$

Hier ist $\begin{align*} \min(u+v,w)=\min(v,w)=w,\min(u,w)=u \end{align*}$ , damit lautet die Behauptung hier $\begin{align*} w\leq u+w \end{align*}$ , ebenfalls offensichtlich erfüllt. Gleichheit tritt hier genau dann ein, wenn $\begin{align*} u=0 \end{align*}$ ist.

3.Fall: $\begin{align*} w\geq v \end{align*}$

Hier ist $\begin{align*} \min(u,w)=u,\min(v,w)=v \end{align*}$ , die Behauptung lautet dann $\begin{align*} \min(u+v,w)\leq u+v \end{align*}$ , was basierend auf der Minimumdefinition ebenfalls klar ist. Gleichheit erfordert hier $\begin{align*} u+v\leq w \end{align*}$ .

Damit ist die Ungleichung (*) gezeigt, und weil das für alle $\begin{align*} p \end{align*}$ so gemacht werden kann, auch die Behauptung a).

Nun zu b), d.h. der Charakterisierung, wann Gleichheit $\begin{align*} \operatorname{ggT}(a\cdot b,n) = \operatorname{ggT}(a,n)\cdot \operatorname{ggT}(b,n) \end{align*}$ gilt, dann kann man aus den diskutierten drei Fällen folgendes, einigermaßen kompliziert klingende Fazit ziehen:

Zitat:

Sei $\begin{align*} e_p(n) \end{align*}$ der Exponent der Primzahl $\begin{align*} p \end{align*}$ in der Primfaktorentwicklung von $\begin{align*} n \end{align*}$ . Dann gilt $\begin{align*} \operatorname{ggT}(a\cdot b,n) = \operatorname{ggT}(a,n)\cdot \operatorname{ggT}(b,n) \end{align*}$ genau dann wenn für jede Primzahl $\begin{align*} p \end{align*}$ , die in den Primfaktorentwicklungen aller (!) drei Zahlen $\begin{align*} a,b,n \end{align*}$ vorkommt, die Bedingung $\begin{align*} e_p(a)+e_p(b)\leq e_p(n) \end{align*}$ erfüllt ist.

Ich denke, das muss man erstmal sacken lassen und begreifen, dass dies tatsächlich so aus 1.-3. oben gefolgert werden kann. Augenzwinkern

Am obigen Beispiel $\begin{align*} a=18,b=12,n=27 \end{align*}$ mal durchexerziert:

Da stellen wir fest, dass lediglich Primzahl $\begin{align*} p=3 \end{align*}$ in allen drei Zahlen $\begin{align*} a,b,c \end{align*}$ als Primfaktor auftritt, also ist die Bedingung $\begin{align*} e_p(a)+e_b(b)\leq e_p(n) \end{align*}$ auch nur dafür zu prüfen. Und da stellen wir $\begin{align*} e_3(18)=2,e_3(12)=1,e_3(27)=3 \end{align*}$ fest, es gilt somit tatsächlich $\begin{align*} e_3(18)+e_3(12)\leq e_3(27) \end{align*}$ (sogar Gleichheit).

10.11.2017, 11:43

Opher19782808

Auf diesen Beitrag antworten »

Jetzt verstehe ich. Ich versuche mich dem gedanklich zu nähern. Die Frage hätte besser heißen müssen.
Gilt Gleichheit für meine Bedingung? (Abschließend ist sie jetzt auch für mich offensichtlich nicht.)

10.11.2017, 11:52

HAL 9000

Auf diesen Beitrag antworten »

Ok, "Wenn a,b teilerfremd und a|n und b|n" gilt, dann gilt die genannte Gleichheit. Aber die Umkehrung gilt nicht, d.h., mit dieser Forderung erwischst du nicht alle Tripel (a,b,n), für die diese Gleichheit gilt, sondern nur einen sehr kleinen Teil.

Tatsächlich würde schon die wesentlich laschere Forderung "Wenn irgendwelche zwei der drei Zahlen a,b,n teilerfremd sind" reichen, damit Gleichheit herrscht, aber auch das (siehe mein Beispiel) erwischt nicht alle solchen Tripel (a,b,c) . Augenzwinkern

10.11.2017, 11:54

Opher19782808

Auf diesen Beitrag antworten »

Vielen Dank für Deine Geduld und Hilfe!

Neue Frage »

Antworten »

Größter gemeinsamer Teiler (Ele. Zahlentheorie)

Verwandte Themen