Zahlentheorie - ggT

04.02.2012, 19:37

ChronoTrigger

Zahlentheorie - ggT

Hallo,

ich hänge gerade an folgender Aufgabe fest:

Zitat:

Sei $\begin{eqnarray*} a \in \mathbb Z \end{eqnarray*}$ . Zeigen Sie:
1) $\begin{eqnarray*} a \text{ ungerade} \implies ggT(3a+4,5a+6)=1 \end{eqnarray*}$
$\begin{eqnarray*} 2) a \text{ gerade} \implies ggT(3a+4,5a+6)=2 \end{eqnarray*}$

Ich weiß noch nicht so recht, wie ich hier anfangen soll. Zuerst hatte ich an den euklidischen Algorithmus gedacht, aber damit komme ich nicht weit. Eine Primfaktorzerlegung kann ich momentan auch nicht erkennen.

Das einzige, was mir noch einfällt, ist, über die Idealdarstellung zu gehen:

$\begin{eqnarray*} <3a+4>+<5a+6> = \{(3a+4) \cdot k + (5a+6) \cdot l | k,l \in \mathbb Z \} \end{eqnarray*}$

$\begin{eqnarray*} =\{a (3k+5l) +4k +6l | k,l \in \mathbb Z \} \end{eqnarray*}$

Hier komme ich allerdings schon nicht mehr weiter.

Kann mir jemand einen Tipp geben?

danke schonmal im voraus.

04.02.2012, 20:00

galoisseinbruder

Auf diesen Beitrag antworten »

Hallo,

das umschreiben in Idealdarstellung stellt dich immer noch vors selbe Problem.
Ich sehe hier nichts besseres als ein bisschen rumprobieren:
Setze a=2k bzw. a=2k+1 und versuche eine Darstellung x(3a+4)+y(5a+6) zu finden in dem dann kein k mehr vorkommt.
Dann noch ein bischen Eigenschaften von ggT verwenden.

05.02.2012, 11:51

ChronoTrigger

Auf diesen Beitrag antworten »

danke, dann versuch ich das mal:

Wenn a gerade ist, schreib ich also $\begin{eqnarray*} a=2k \end{eqnarray*}$ und habe dann mit dem Lemma von Bezout folgendes:

$\begin{eqnarray*} ggT(3a+4,5a+6)=ggT(6k+4,10k+6)=x(6k+4)+y(10k+6)=k(6x+10y)+(4x+6y)<br /> \end{eqnarray*}$

Ich seh aber momentan nicht, wie ich hier das k wegbekommen könnte.

06.02.2012, 09:04

ChronoTrigger

Auf diesen Beitrag antworten »

Ich sehe leider momentan immer noch nicht, wie ich bei der Aufgabe weiter kommen kann.

hast du vielleicht noch einen tipp für mich?

06.02.2012, 09:11

René Gruber

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 5a+6 \end{eqnarray*}$ ist gewiss nicht durch 5 teilbar, also gilt

$\begin{eqnarray*} \operatorname{ggT}(3a+4,5a+6) = \operatorname{ggT}(5(3a+4),5a+6) = \operatorname{ggT}(15a+20-3(5a+6),5a+6) = \operatorname{ggT}(2,5a+6) = 1 \end{eqnarray*}$

erst im letzten Schritt wird die Ungeradheit von $\begin{eqnarray*} a \end{eqnarray*}$ benutzt.

06.02.2012, 09:46

ChronoTrigger

Auf diesen Beitrag antworten »

danke, darauf wäre ich wohl nie im Leben gekommen

der fall, dass a gerade ist, müsste dann analog gehen, bis zum letzten schritt. Dort ist dann $\begin{eqnarray*} 5a+6 \end{eqnarray*}$ gerade, und somit $\begin{eqnarray*} ggT(2,5a+6)=2 \end{eqnarray*}$ .

06.02.2012, 09:55

René Gruber

Auf diesen Beitrag antworten »

Man kann aber auch ganz normal den Euklidischen Algorithmus durchziehen, es dauert nur länger:

$\begin{eqnarray*} \operatorname{ggT}(3a+4,5a+6) &=& \operatorname{ggT}(3a+4,5a+6-(3a+4)) = \operatorname{ggT}(3a+4,2a+2) = \operatorname{ggT}(3a+4-(2a+2),2a+2)\\ &=& \operatorname{ggT}(a+2,2a+2) = \operatorname{ggT}(a+2,2a+2-2(a+2)) = \operatorname{ggT}(a+2,-2) \end{eqnarray*}$

Neue Frage »

Antworten »

Zahlentheorie - ggT

Verwandte Themen