Mindevice Logo

Erweiterter euklidischer Algorithmus

Sei a,b∈Z,a=252,b=198\text{Sei } a, b \in \mathbb{Z}, a = 252, b = 198

ggt(252,198)=18=252⋅4+198⋅−5\text{ggt}(252, 198)=18=252 \cdot 4 + 198 \cdot -5

Rechenweg

252=1×198+54(λ=0,μ=1)198=3×54+36(λ=1,μ=−1)54=1×36+18(λ=−3,μ=4)36=2×18+0(λ=4,μ=−5)\begin{aligned}252 &= 1 \times 198 + 54 \qquad (\lambda = 0, \mu = 1) \\198 &= 3 \times 54 + 36 \qquad (\lambda = 1, \mu = -1) \\54 &= 1 \times 36 + 18 \qquad (\lambda = -3, \mu = 4) \\36 &= 2 \times 18 + 0 \qquad (\lambda = 4, \mu = -5) \\\end{aligned}

Was ist der Erweiterter euklidischer Algorithmus?

Der erweiterte euklidische Algorithmus berechnet den größten gemeinsamen Teiler (ggT) von zwei Zahlen, in diesem Fall 252 und 198. Der Algorithmus liefert zusätzlich die Koeffizienten λ und μ, sodass der ggT als lineare Kombination der beiden Zahlen dargestellt werden kann:

ggT(252,198)=18=252⋅4+198⋅−5\text{ggT}(252, 198)=18=252 \cdot 4 + 198 \cdot -5

In diesem Fall ist der ggT von 252 und 198 gleich 18. Die Gleichung für den ggT kann als:

18=252⋅4+198⋅−518 = 252 \cdot 4 + 198 \cdot -5

Dieser Ausdruck zeigt, wie der ggT durch eine lineare Kombination der beiden Zahlen dargestellt werden kann, wobei λ = 4 und μ = -5.