TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 53

Aus VoWi
Zur Navigation springen Zur Suche springen

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

Hilfreiches[Bearbeiten]

Größter gemeinsamer Teiler
Größter gemeinsamer Teiler[Bearbeiten, WP, 1.14 Definition]

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[Bearbeiten]


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

Größster gemeinsamer Teiler ist 1.