Bestimmen Sie jeweils den größten gemeinsamen Teiler c der folgenden Zahlen sowie x, y ∈ ℤ mit x · a+y · b=c mit …

Question

Text erkannt:

Bestimmen Sie jeweils den größten gemeinsamen Teiler $c$ der folgenden Zahlen sowie $x, y \in \mathbb{Z}$ mit $x \cdot a+y \cdot b=c$ mit Hilfe des Euklidischen Algorithmus':
(a) $a=34, b=1615$
(b) $a=143, b=825$
(c) $a=4919, b=53$
(d) $a=1048576, b=16384$

Aufgabe:

Answer 1

Hallo

den euklidischen Algorithmus solltest du doch kennen?

Beispiel b)

825=5*143+110

143=1*110+33

110=3*33+11

33=3*11

also ggT=11

Probe damit man sich nicht verrechnet hat: 825 uns 143 sind durch 11 teilbar

entsprechend die anderen

Gruß lul

Comments

Ich habe noch eine weiterführende Frage dazu:

Für welchen Input für allgemeine a,b Elemente von N terminiert der Euklidischen Algorithmus nach nur einem Schritt?

Bisher habe ich nur rausgefunden für vielfache des Teilers (b) also bspw a = 25 und b = 5. Gibt es noch weitere?

---

Hallo

du hast recht, nur wenn a=n*b ist braucht man nur einen Schritt, Beispiel a) ist ein einfaches mit 2 Schritten.

lul

Answer 2

zu a) als Beispiel:

Die Rechnung "größere - kleinere Zahl" klappt für 1615 und 34 zunächst 47 mal:

1615-47·34=17

34-17=17

Damit ist 17 der gemeinsame Teiler und es gilt:

17=1·1615 - 34·47.