ggT	Neue Frage »

02.12.2006, 21:30

Celly

ggT

Hallo!

Ich habe hier eine Aufgabe, bei der ich nicht weiter komme. Vielleicht kann mir ja jemand hier weiterhelfen?!

Sie lautet:

Seien $\begin{eqnarray*} a,b \in \mathbb N \end{eqnarray*}$ und ggT(a,b)=1 (N ohne die 0)

Beweisen Sie: ggT(a+b,a-b) $\begin{eqnarray*} \in \{ 1,2\} \end{eqnarray*}$

Hier meine "Überlegungen":

Seien $\begin{eqnarray*} a= \prod_{i=1}^\infty~p_{i}^{n_{i}} \end{eqnarray*}$ und $\begin{eqnarray*} b= \prod_{i=1}^\infty~p_{i}^{m_{i}} \end{eqnarray*}$

ggT(a,b)=1 , d.h. $\begin{eqnarray*} \prod_{i=1}^\infty~p_{i}^{min(n_{i},m_{i})} = 1 \end{eqnarray*}$

=> $\begin{eqnarray*} min(n_{i},m_{i}) = 0 \end{eqnarray*}$ für alle i

Das heisst es gibt die Fälle:

i) a=1 und b=1 Da ist mir der Beweis klar
ii) a=1 und b $\begin{eqnarray*} \neq \end{eqnarray*}$ 1 Auch hier ist es mir klar
iii) a $\begin{eqnarray*} \neq \end{eqnarray*}$ 1 und b= 1 Auch hier ist es klar

Dann kommt noch der 4. Fall:

a $\begin{eqnarray*} \neq \end{eqnarray*}$ 1 und b $\begin{eqnarray*} \neq \end{eqnarray*}$ 1

Dann folgt:

$\begin{eqnarray*} n_{i} =0 \end{eqnarray*}$ für bestimmte i und $\begin{eqnarray*} m_{i} \neq 0 \end{eqnarray*}$ für genau diese i's. ( Weiß nicht genau wie ich das ausdrücken soll!) Und $\begin{eqnarray*} m_{i} =0 \end{eqnarray*}$ für bestimmte i und $\begin{eqnarray*} n_{i} \neq 0 \end{eqnarray*}$ für genau diese i's.

Dann ist

$\begin{eqnarray*} a +b = \prod_{i=1}^\infty~p_{i}^{n_{i}} + \prod_{i=1}^\infty~p_{i}^{m_{i}} \end{eqnarray*}$

und $\begin{eqnarray*} a -b = \prod_{i=1}^\infty~p_{i}^{n_{i}} - \prod_{i=1}^\infty~p_{i}^{m_{i}} \end{eqnarray*}$

So und nun komm ich nicht weiter!! Wie kann ich da jetzt auf den ggT schließen??? Ich kann dann a+b und a-b nicht weiter zusammenfassen! Ist das überhaupt notwendig!?

Ich weiß nicht nicht weiter! Vielleicht kann mir jemand helfen?

02.12.2006, 22:07

Auf diesen Beitrag antworten »

Grundregel: Je einfacher, desto besser - also mach's nicht so kompliziert. Die hilfreichste Regel bei den ggT-Umformungen ist immer noch

$\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a,b-ka) \end{eqnarray*}$

für beliebige ganze Zahlen $\begin{eqnarray*} a,b,k \end{eqnarray*}$ . Im vorliegenden Fall kann das etwa so aussehen:

$\begin{eqnarray*} g:=\operatorname{ggT}(a+b,a-b) = \operatorname{ggT}(a+b,a-b+(a+b)) = \operatorname{ggT}(a+b,2a) \end{eqnarray*}$ ,

also $\begin{eqnarray*} g|(2a) \end{eqnarray*}$ . Analog folgt $\begin{eqnarray*} g|(2b) \end{eqnarray*}$ , insgesamt also $\begin{eqnarray*} g|\operatorname{ggT}(2a,2b) \end{eqnarray*}$ . Wegen

$\begin{eqnarray*} \operatorname{ggT}(2a,2b) = 2\operatorname{ggT}(a,b) = 2 \end{eqnarray*}$

ist damit $\begin{eqnarray*} g|2 \end{eqnarray*}$ , fertig.

02.12.2006, 22:18

Celly

Auf diesen Beitrag antworten »

Erstmal dankeschön für die Antwort!!

Hätt aber trotzdem noch ein paar Fragen...

Diese Regel

ggT(a,b) = ggT (a,b-ka)

haben wir, denk ich, noch nicht gehabt?!!! Oder ich erkenn sie einfach nicht?! Warum ist das denn so?? Für k=0 ists mir noch klar ;-) Aber das wars dann auch.

Noch eine kleine Frage:

ggT(2a,2b) = 2 ggT(a,b) =2

Auch das haben wir noch nicht "gelernt". Ich versteh schon warum, aber ich müsste das denk ich "beweisen" wenn ich das benutze.

02.12.2006, 22:23

Celly

Auf diesen Beitrag antworten »

Ich denk ich hab die Regeln gefunden!!?!!

Hat das was damit zu tun, dass ja für a,b $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$

a= q*b+r mit q,r $\begin{eqnarray*} \in \mathbb N \end{eqnarray*}$ und 0<=r<b

ist??

02.12.2006, 22:24

Celly

Auf diesen Beitrag antworten »

Das hab ich auch noch vergessen!:

Denn wir haben i.d. Vorlesung schon mal gezeigt, dass dann:

ggT(a,b) = ggT(b,r) ist

02.12.2006, 22:31

Auf diesen Beitrag antworten »

Ja, das ist es. Hier nochmal ein eigenständiger Beweis:

(I) Sei $\begin{eqnarray*} r \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} \operatorname{ggT}(a,b) \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} r \end{eqnarray*}$ sowohl Teiler von $\begin{eqnarray*} a \end{eqnarray*}$ als auch von $\begin{eqnarray*} b \end{eqnarray*}$ , d.h., es gibt ganze Zahlen $\begin{eqnarray*} a',b' \end{eqnarray*}$ mit $\begin{eqnarray*} a=ra',b=rb' \end{eqnarray*}$ . Es folgt $\begin{eqnarray*} b-ka = r(b'-ka') \end{eqnarray*}$ , also ist $\begin{eqnarray*} r \end{eqnarray*}$ auch Teiler von $\begin{eqnarray*} b-ka \end{eqnarray*}$ , insgesamt also Teiler von $\begin{eqnarray*} \operatorname{ggT}(a,b-ka) \end{eqnarray*}$ .

(II) Sei $\begin{eqnarray*} r \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} \operatorname{ggT}(a,b-ka) \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} r \end{eqnarray*}$ sowohl Teiler von $\begin{eqnarray*} a \end{eqnarray*}$ als auch von $\begin{eqnarray*} b-ka \end{eqnarray*}$ , d.h., es gibt ganze Zahlen $\begin{eqnarray*} a',c' \end{eqnarray*}$ mit $\begin{eqnarray*} a=ra',b-ka=rc' \end{eqnarray*}$ . Es folgt $\begin{eqnarray*} b = (b-ka)+ka = rc'+kra' = r(c'+ka') \end{eqnarray*}$ , also ist $\begin{eqnarray*} r \end{eqnarray*}$ auch Teiler von $\begin{eqnarray*} b \end{eqnarray*}$ , insgesamt also Teiler von $\begin{eqnarray*} \operatorname{ggT}(a,b) \end{eqnarray*}$ .

Damit ist gezeigt, das jeder Teiler von $\begin{eqnarray*} \operatorname{ggT}(a,b) \end{eqnarray*}$ auch Teiler von $\begin{eqnarray*} \operatorname{ggT}(a,b-ka) \end{eqnarray*}$ ist, und umgekehrt. Da beides nichtnegative ganze Zahlen sind, sind sie somit identisch.

Das zweite

$\begin{eqnarray*} \operatorname{ggT}(ka,kb) = k\operatorname{ggT}(a,b) \end{eqnarray*}$

beweist du aber selbst, das ist noch einfacher.

02.12.2006, 22:38

Celly

Auf diesen Beitrag antworten »

Ok! Dankeschön!!

Eine Frage hätt ich noch:

ggT(a+b,a-b) = ggT(a+b,a-b + (a+b))

Da ist ja dann k=-1 oder??? Wieso darf man das denn einfach annehmen? Weil die Formel für alle k gilt??

02.12.2006, 22:40

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
$\begin{eqnarray*} \operatorname{ggT}(a,b) = \operatorname{ggT}(a,b-ka) \end{eqnarray*}$

für beliebige ganze Zahlen $\begin{eqnarray*} a,b,k \end{eqnarray*}$ .

$\begin{eqnarray*} k=-1 \end{eqnarray*}$ ist eine ganze Zahl, ja.

02.12.2006, 22:42

Celly

Auf diesen Beitrag antworten »

Ok!

Dankeschön nochmal für die Hilfe!!!!! Gott

Neue Frage »

Antworten »

ggT

Verwandte Themen