Größten gemeinsamen Teiler d = GGT(a, b) und r und s berechnen

Question

Aufgabe:Berechnen Sie den größten gemeinsamen Teiler d = ggT(a, b) und gewisse ganze Zahlen r, s mit d = r · a + s · b für
(a) a = 362 ∧ b = 22

Problem/Ansatz

Ich verstehe wie man den GGT mit dem euklidischen Algorithmus berechnet. Ich verstehe aber nicht , wie  d = r · a + s · b berechnet wird und was r und was s ist.

Könnte mir jemand dabei helfen?

Answer 1

Aloha :)

Mit dem Euklidischen Algorithmus bekommst du:$$d=\text{ggT}(362\,,\,22)=\text{ggT}(22\,,\,362\,\text{mod}\,22)=\text{ggT}(22\,,\,10)$$$$\phantom{d}=\text{ggT}(10\,,\,22\,\text{mod}\,10)=\text{ggT}(10\,,\,2)=\text{ggT}(2\,,\,10\,\text{mod}\,2)$$$$\phantom{d}=\text{ggT}(2\,,\,0)=2$$Alternativ zur modulo-Division (also dem Rest der Division) kann man auch subtrahieren, das benötigt aber viel mehr Schritte ;)

Nun sollst du noch den ggT als Linearkombination von 362 und 22 schreiben, wobei als Koeffizienten nur ganze Zahlen \(r\) und \(s\) zugelassen sind:$$2=r\cdot362+s\cdot22$$Dazu betrachte:$$\begin{array}{c}362 &=& 16\cdot 22 & +&10 &\quad\Rightarrow\quad&10&=&362&-&16\cdot22\\22 &=& 2\cdot 10 & +&2&\Rightarrow & 2 &=&22&-&2\cdot10\end{array}$$Damit erhältst du:$$2=22-2\cdot10=22-2\cdot(362-16\cdot22)=22-2\cdot362+32\cdot22$$$$\Rightarrow\quad2=(-2)\cdot362+33\cdot22$$