de
Seitenbanner
Menu
A-Z
Aufgaben

Erweiterter euklidischer Algorithmus – Interaktiver Aufgabengenerator

Artikel zum Nachlesen: Erweiterter euklidischer Algorithmus

Der interaktive Aufgabengenerator zum Thema Erweiterter euklidischer Algorithmus erzeugt dir eine unbegrenzte Anzahl an individuell anpassbaren, prozedural generierten Übungsaufgaben. Er unterstützt dich dabei, die Aufgaben zu lösen, das Thema ausgiebig zu üben und zu verstehen. Hierzu erstellt der Generator für jede Aufgabe eine ausführliche, verständliche Schritt-für-Schritt Musterlösung und bietet dir zudem die Möglichkeit, deine eigenen Lösungen direkt zu überprüfen. Alle Lösungen und Lösungswege werden deterministisch mithilfe der zugrundeliegenden mathematischen Verfahren berechnet. 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

Die ausgewählten Beispiele ermöglichen es dir, einige Generator-Konfigurationen und die verfügbare Unterstützung beim Lösen der Aufgaben unverbindlich und in aller Ruhe kennenzulernen.

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

Aufgabe 2 von 2

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

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

Aufgabengenerator

Der Aufgabengenerator ermöglicht es dir, beliebig viele, an deine individuellen Bedürfnisse angepasste Aufgaben zu generieren, um dich perfekt mit dem Thema vertraut zu machen.

Melde dich an, um unbegrenzt Übungsaufgaben zu erzeugen. Jetzt anmelden!
Konfiguration anpassen

Konfiguriere den Aufgabengenerator nach deinen Wünschen – von einfachen Beispielen bis zu anspruchsvollen Herausforderungen.

Lege die minimale und die maximale Anzahl an Schritten für den euklidischen Algorithmus (jeweils von 1 bis 10) und den maximalen Quotienten pro Schritt (von 1 bis 10) fest.

 – 
Hier könnte deine generierte Aufgabe stehen!
Eigene Aufgabe

Eigene Aufgabe verwenden

Löse deine eigenen Aufgaben oder lasse deiner Neugier freien Lauf – mit voller Unterstützung des Generators.

Melde dich an, um deine eigenen Aufgaben zu verwenden und zu lösen. Jetzt anmelden!

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: Beispielaufgabe 1 von 2

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

Musterlösung: Beispielaufgabe 2 von 2

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

\[\begin{align*}
152 &= 3 \cdot 42 + 26 \\[0.5em]
42 &= 1 \cdot 26 + 16 \\[0.5em]
26 &= 1 \cdot 16 + 10 \\[0.5em]
16 &= 1 \cdot 10 + 6 \\[0.5em]
10 &= 1 \cdot 6 + 4 \\[0.5em]
6 &= 1 \cdot 4 + 2 \\[0.5em]
4 &= 2 \cdot 2 + 0
\end{align*}\]

Der größte gemeinsame Teiler $ 2$ 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*}
2&= 1 \cdot 6-1 \cdot 4 \\[0.5em]
&=1 \cdot 6-1 \cdot (10 - 1 \cdot 6) \\[0.5em]
&=-1 \cdot 10 + 2 \cdot 6 \\[0.5em]
&=-1 \cdot 10 + 2 \cdot (16 - 1 \cdot 10) \\[0.5em]
&=2 \cdot 16-3 \cdot 10 \\[0.5em]
&=2 \cdot 16-3 \cdot (26 - 1 \cdot 16) \\[0.5em]
&=-3 \cdot 26 + 5 \cdot 16 \\[0.5em]
&=-3 \cdot 26 + 5 \cdot (42 - 1 \cdot 26) \\[0.5em]
&=5 \cdot 42-8 \cdot 26 \\[0.5em]
&=5 \cdot 42-8 \cdot (152 - 3 \cdot 42) \\[0.5em]
&=-8 \cdot 152 + 29 \cdot 42
\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(152, 42\bigr) = 2 &= -8 \cdot 152 + 29 \cdot 42 \\[1em]
\implies s &= -8 \\[0.5em]
t &= 29
\end{align*}\]
Lösung überprüfen

Eigene Lösung überprüfen: Beispielaufgabe 1 von 2

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

Eigene Lösung überprüfen: Beispielaufgabe 2 von 2

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