0 Daumen
488 Aufrufe

Unbenannt1.PNG

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:

Avatar von

2 Antworten

+1 Daumen

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

Avatar von 106 k 🚀

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

0 Daumen

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.

Avatar von 123 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community