TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 53

Man bestimme den $\text{ggT}(1109,4999)$ mit Hilfe des Euklidischen Algorithmus.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Größter gemeinsamer Teiler

Größter gemeinsamer Teiler

Der größte gemeinsame Teiler (ggT) von zwei ganzen Zahlen $a$ und $b$ ist die größte positive natürliche Zahl, die Teiler beider Zahlen ist. Die Vielfachheit jeder Primzahl $p$ im größten gemeinsamen Teiler entspricht dem Minimum der Vielfachheiten von $p$ in $a$ und $b$. $\text{ggT}(a,b):=\prod _{p\in \mathbb{P}}{p}^{min({\nu }_p(a),{\nu }_p(b))}$

Euklidischer Algorithmus

Lösungsvorschlag von samuelp

$\begin{array}{cc}4999& =4\cdot 1109+563\\ 1109& =1\cdot 563+546\\ 563& =1\cdot 546+17\\ 546& =32\cdot 17+2\\ 17& =8\cdot 2+1\\ 2& =2\cdot 1+0\end{array}$

Größster gemeinsamer Teiler ist 1.