de
Seitenbanner
Menu
Aufgaben

Aufgaben zum erweiterten euklidischen Algorithmus

Der interaktive Aufgabengenerator zum Thema Erweiterter euklidischer Algorithmus erstellt dir eine unbegrenzte Anzahl an individuell anpassbaren Aufgaben 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 deine eigenen Aufgaben verfügbar.

Aufgabe 1 von 2

Bestimme 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) \]



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*}\]