de
Seitenbanner
Menu
A-Z
Aufgaben

Erweiterter euklidischer Algorithmus – Interaktiver Aufgabengenerator mit Musterlösungen

Artikel zum Nachlesen: Erweiterter euklidischer Algorithmus

Der interaktive Aufgabengenerator zum Thema Erweiterter euklidischer Algorithmus erzeugt dir eine unbegrenzte Anzahl an individuell anpassbaren Übungsaufgaben und Beispielen. Er unterstützt dich dabei, diese zu lösen und das Thema ausgiebig zu üben. Hierzu erstellt der Generator für jede Aufgabe eine ausführliche, verständliche Musterlösung und bietet dir zudem die Möglichkeit, deine eigenen Lösungen direkt zu überprüfen. Sämtliche Hilfestellungen stehen sowohl für die freien Beispiele als auch für generierte und eigene Aufgaben im vollen Umfang zur Verfügung.

Aufgabe erstellen

Beispielaufgaben

Beispielaufgaben

Aufgabe 1 von 2

Bestimme mithilfe des erweiterten euklidischen Algorithmus ganzzahlige Koeffizienten $s, t \in \Z$, so dass die folgende Gleichung erfüllt ist.

\[s \cdot 17 + t \cdot 12 = \operatorname{ggT}\bigl(17,12\bigr)\]
Aufgabengenerator

Aufgabengenerator

Konfiguration anpassen
 – 
Eigene Aufgabe

Eigene Aufgabe verwenden

Gib die ganze Zahlen $a$ und $b$ ein, für die mithilfe des erweiterten euklidischen Algorithmus ganzzahlige Koeffizienten $s,t \in \Z$ mit $s \cdot a + t \cdot b = \ggT(a,b)$ berechnet werden sollen.

Aufgabe lösen

Musterlösung

Musterlösung

Zum Bestimmen der Koeffizienten $s$ und $t$ muss zunächst der größte gemeinsame Teiler von $ 17$ und $ 12$ mithilfe des euklidischen Algorithmus bestimmt werden.

\[\begin{align*}
17 &= 1 \cdot 12 + 5 \\[0.5em]
12 &= 2 \cdot 5 + 2 \\[0.5em]
5 &= 2 \cdot 2 + 1 \\[0.5em]
2 &= 2 \cdot 1 + 0
\end{align*}\]

Der größte gemeinsame Teiler $ 1$ kann wie üblich an der vorletzten Zeile abgelesen werden. Die gesuchten Koeffizienten $s$ und $t$ können durch Rückwärtseinsetzen gefunden werden.

\[\begin{align*}
1&= 1 \cdot 5-2 \cdot 2 \\[0.5em]
&=1 \cdot 5-2 \cdot (12 - 2 \cdot 5) \\[0.5em]
&=-2 \cdot 12 + 5 \cdot 5 \\[0.5em]
&=-2 \cdot 12 + 5 \cdot (17 - 1 \cdot 12) \\[0.5em]
&=5 \cdot 17-7 \cdot 12
\end{align*}\]

Die gesuchten Koeffizienten $s$ und $t$ können an der letzten durch das Rückwärtseinsetzen erhaltenen Gleichung direkt abgelesen werden.

\[\begin{align*}
\operatorname{ggT}\bigl(17, 12\bigr) = 1 &= 5 \cdot 17-7 \cdot 12 \\[1em]
\implies s &= 5 \\[0.5em]
t &= -7
\end{align*}\]
Lösung überprüfen

Eigene Lösung überprüfen

Gib die berechneten Parameter $s$ und $t$ ein.