de
Seitenbanner
Menu
A-Z
Aufgaben

Aufgaben zum erweiterten euklidischen Algorithmus

Artikel zum Nachlesen: Erweiterter euklidischer Algorithmus

Der interaktive Aufgabengenerator zum Thema Erweiterter euklidischer Algorithmus erstellt dir eine unbegrenzte Anzahl an individuell anpassbaren Aufgaben und Beispielen und unterstützt dich dabei, diese zu bearbeiten und zu lösen – unter anderem durch ausführliche und verständliche Musterlösungen . Darüber hinaus ist dieselbe Unterstützung auch für eigene Aufgaben verfügbar.

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 = \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\cdot5-2\cdot2 \\[0.5em]
&=1\cdot5-2\cdot(12-2\cdot5) \\[0.5em]
&=-2\cdot12+5\cdot5 \\[0.5em]
&=-2\cdot12+5\cdot(17-1\cdot12) \\[0.5em]
&=5\cdot17-7\cdot12
\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*}
\ggT\bigl(17, 12\bigr) = 1 &= 5 \cdot 17-7 \cdot 12 \\[1em]
\Rightarrow 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.