+1 Daumen
964 Aufrufe

1) Bestimme den größten gemeinsamen Teiler der Zahlen a = 198 und b = 315 auf zwei verschiedene Weisen:
- mit der Primfaktorzerlegung der beiden Zahlen bestimmen und daraus den ggT ermitteln.

- mit dem euklidischen Algorithmus


- eine dritte frei nach Wahl

2) Führe den euklidischen Algorithmus auch für : a = 49024 und b = 23408.


3) Bestimme für die Zahlen a und b aus 1) und 2) jeweils eine Darstellung des größten gemeinsamen Teilers als Linearkombination der Zahlen a und b, d. h. bestimme u, v ∈ Z so, dass gilt:
ggT (a, b) = u · a + v · b.

von

2 Antworten

+3 Daumen
 
Beste Antwort

Hallo Nadia, hallo Lina,

Der euklidische Algorithmus war:$$\begin{aligned} 315 \div 198 &= 1 \space \text{Rest}\, &117 \\ 198 \div 117 &= 1 \space \text{Rest}\, &81 \\ 117 \div 81 &= 1 \space \text{Rest}\, &36 \\ 81 \div 36 &= 2 \space \text{Rest}\, &9 \\ 36 \div 9 &= 4 \space \text{Rest}\, &0 \end{aligned}$$

3) Bestimme für die Zahlen a und b aus 1) und 2) jeweils eine Darstellung des größten gemeinsamen Teilers als Linearkombination der Zahlen a und b, d. h. bestimme u, v ∈ Z so, dass gilt:
ggT (a, b) = u · a + v · b.

Eine der letzten Gleichungen aus dem euklidischen Algorithmus zur Bestimmung des ggT von 198 und 315 lautet$$81 : 36 = 2 \space \text{Rest}\, 9 \\ \implies 9 = 1 \cdot 81 - 2 \cdot \colorbox{#ffff00}{36}$$damit liegt bereits eine Linearkombination für den \(\text{ggT} = 9\) vor. Nun ersetzt man rückwärts jeweils eine Zahl (hier die \(\colorbox{#ffff00}{36}\)) aus den Ergebnissen des euklidischen Algorithmus.

Die vorhergehende Division war \(117 \div 81 = 1 \space \text{Rest}\, \colorbox{#ffff00}{36}\) daraus folgt:

$$ \colorbox{#ffff00}{36} = 117 - 1 \cdot 81$$

Einsetzen in die Gleichung mit \(9=\dots\) gibt:

$$\begin{aligned} 9 &= 1 \cdot 81 - 2 \cdot( 1 \cdot 117 - 1 \cdot 81) \\ &= -2 \cdot 117 + 3 \cdot \colorbox{#ff88ff}{81} \end{aligned}$$

Aus \(198 \div 117 = 1 \space \text{Rest}\, \colorbox{ff88ff}{81} \) (s.o.) folgt

$$ \colorbox{#ff88ff}{81} = 198 - 1 \cdot 117 $$

wieder Einsetzen in die aktuelle Gleichung des ggT:

$$\begin{aligned} 9 &= -2 \cdot 117 + 3 \cdot(198 - 1 \cdot 117) \\ &= 3 \cdot 198 - 5 \cdot \colorbox{#88ff88}{117} \end{aligned}$$

und die 117 folgt aus der ersten Gleichung \(315 \div 198 = 1 \space \text{Rest}\, \colorbox{#88ff88}{117}\):

$$ \colorbox{#88ff88}{117} = 315 - 1 \cdot 198 $$

Einsetzen:

$$\begin{aligned} 9 &= 3 \cdot 198 - 5 \cdot( 315 - 1 \cdot 198) \\ &= -5 \cdot 315 + 8 \cdot 198\end{aligned}$$

und damit erhält man eine Linearkombination für den \(\text{ggT} = 9\) aus den ursprünglichen Zahle \(a=198\) und \(b=315\).

Falls noch etwas unklar bleiben sollte, so frage nochmal nach.

Gruß Werner

von 48 k
+1 Daumen

Euklidischen Algorithmus

ggT(198, 315)
315 : 198 = 1 Rest 117
198 : 117 = 1 Rest 81
117 : 81 = 1 Rest 36
81 : 36 = 2 Rest 9
36 : 9 = 4 Rest 0
Damit ist 9 der ggT.
von 477 k 🚀

Der euklidische Algorithmus:

315 = 198*1 + 117
198 = 117*1 + 81
117 = 81*1 + 36
81 = 36*2 + 9
36 = 9*4 + 0

Erweiterung von unten nach oben,
beginnend mit der vorletzten Zeile: 

9
= 81 - 36*2 = 81 - (117-81*1)*2 = 81*3 - 117*2
= (198-117*1)*3 - 117*2 = 198*3 - 117*5
= 198*3 - (315-198*1)*5 = 198*8 - 315*5 = 9.

kann mir bitte jemand wenigstens die letzte erklären, den Rest habe ich jetzt schon gemacht :)

Was hast du an der Antwort von "Gast az0815" nicht verstanden.

315 : 198 = 1 Rest 117 → 117 = 315 - 1·198 → 9 = 3·198 - 5·117 = 3·198 - 5·(315 - 1·198) = 8·198 - 5·315
198 : 117 = 1 Rest 81 → 81 = 198 - 1·117 → 9 = 3·(198 - 1·117) - 2·117 = 3·198 - 5·117
117 : 81 = 1 Rest 36 → 36 = 117 - 1·81 → 9 = 81 - 2·(117 - 1*81) = 3·81 - 2·117
81 : 36 = 2 Rest 9 → 9 = 81 - 2·36
36 : 9 = 4 Rest 0

Also ist 9 = 8·198 - 5·315

ist das die letze Aufgabe ?

Zumindest die hälfte. Ich habe es für den ggt von 9 vorgemacht. Also für das Beispiel 1)

Du solltest es auch noch für 2) machen. Und dort auch den ggt berechnen.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community