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

Man bestimme den ${\textrm {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$. ${\textrm {ggT}}(a,b):=\prod _{p\in \mathbb {P} }p^{\min(\nu _{p}(a),\;\nu _{p}(b))}$

Euklidischer Algorithmus

Lösungsvorschlag von samuelp

${\begin{aligned}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{aligned}}$

Größster gemeinsamer Teiler ist 1.