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

Aus VoWi
Zur Navigation springen Zur Suche springen

Man bestimme den ggT (2008, 6318) mit Hilfe des Euklidischen Algorithmus

Angabe SS 08 geändert ggT (2008,6316), sonst analog wie unten

Hapi

SS08 Beispiel 8

ggT(2008, 6318)

6318 = 2008*3 + 294

2008 = 294*6 + 244

294 = 244*1 + 50

244 = 50*4 + 44

50 = 44*1 + 6

44 = 6*7 + 2

6 = 2*3+0

ggT = 2

ggT(2008, 6316)

6316 = 2008*3 + 292

2008 = 292*6 + 256

292 = 256*1 + 36

256 = 36*7 + 4

36 = 4*9 + 0

ggT = 4