Euklidischer Algorithmus

Der euklidische Algorithmus ist ein Rechenverfahren zur Bestimmung des größten gemeinsamen Teilers von zwei natürlichen Zahlen. Dabei wird so oft Division mit Rest durchgeführt, bis der Rest 0 ist. Der größte gemeinsame Teiler ist dann die zweite Zahl rechts des =-Zeichens. Beispiel: Bestimmung von g g T ( 42, 22 ) MathType@MTEF@& 053;@& 053;@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbdfgBPj MCPbqeduuDJXwAKbYu51MyVXgaruWqVvNCPvMCG4uz3bqefqvATv2C G4uz3bIuV1wyUbqeeuuDJXwAKbsr4rNCHbGeaGqiVu0Je9sqqrpepC 0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yq aqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeaacaGaaiaabe qaamaaeaqbaaGcbaaceaGaa83zaiaa=DgacaWFubWaaeWaaeaacaaI 0aGaaGOmaiaacYcacaqGGaGaaeOmaiaabkdaaiaawIcacaGLPaaaaa a@455E@ 42 = 1 ⋅ 22 + 20 22 = 1 ⋅ 20 + 2 20 = 10 ⋅ 2 + 0 MathType@MTEF@& 053;@& 053;@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbdfgBPj MCPbqeduuDJXwAKbYu51MyVXgaruWqVvNCPvMCG4uz3bqefqvATv2C G4uz3bIuV1wyUbqeeuuDJXwAKbsr4rNCHbGeaGqiVu0Je9sqqrpepC 0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yq aqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeaacaGaaiaabe qaamaaeaqbaaGceaabbeaacaaI0aGaaGOmaiaabccacaqG9aGaaeii aiaabgdacqGHflY1caqGYaGaaeOmaiabgUcaRiaaikdacaaIWaaabq aWaiaaikdacaaIYaGaaeiiaiaab2dacaqGGaGaaeymaiabgwSixlaa bkdacaqGWaGaey4kaSIaaGOmaaqaeamacaaIYaGaaGimaiaabccaca qG9aGaaeiiaiaabgdacaqGWaGaeyyXICneeG+aaaaaai1B0bWdbiaa ikdaqaaNa8LaBdWdciabgUcaRiaaicdaaaaa@6004@ Jetzt ist der Rest gleich 0 MathType@MTEF@& 053;@& 053;@+= fea