Erweiterter euklidischer Algorithmus

Ist ein Verfahren, mit dessen Hilfe sich neben dem größten gemeinsamen Teiler von zwei natürlichen Zahlen a und b zusätzlich zwei ganze Zahlen s und t berechnen lassen, welche die folgende Gleichung erfüllen: g g T ( a , b ) = s ⋅ a + t ⋅ b MathType@MTEF@& 053;@& 053;@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbdfgBPj MCPbqeduuDJXwAKbYu51MyVXgaruWqVvNCPvMCG4uz3bqefqvATv2C G4uz3bIuV1wyUbqeeuuDJXwAKbsr4rNCHbGeaGqiVu0Je9sqqrpepC 0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yq aqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeaacaGaaiaabe qaamaaeaqbaaGcbaaceaGaa83zaiaa=DgacaWFubWaaeWaaeaacaWG HbGaaeilaiaabccacaqGIbaacaGLOaGaayzkaaGaaeiiaiaab2daca qGGaGaae4CaiabgwSixlaabggacqGHRaWkcaWG0bGaeyyXICTaamOy aaaa@4F7A@ Der erweiterte euklidische Algorithmus läuft am Beispiel a = 96 MathType@MTEF@& 053;@& 053;@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbdfgBPj MCPbqeduuDJXwAKbYu51MyVXgaruWqVvNCPvMCG4uz3bqefqvATv2C G4uz3bIuV1wyUbqeeuuDJXwAKbsr4rNCHbGeaGqiVu0Je9sqqrpepC 0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yq aqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeaacaGaaiaabe qaamaaeaqbaaGcbaGaamyyaiaabccacaqG9aGaaeiiaiaabMdacaqG 2aaaaa@414E@ und b = 76 MathType@MTEF@& 053;@& 053;@+= feaagKart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbdfgBPj MCPbqeduuDJXwAKbYu51MyVXgaruWqVvNCPvMCG4uz3bqefqvATv2C G4uz3bIuV1wyUbqeeuuDJXwAKbsr4rNCHbGeaGqiVu0Je9sqqrpepC 0xbbL8F4rqqrFfpeea0xe9Lq=Jc9vqaqpepm0xbba9pwe9Q8fs0=yq aqpepae9pg0FirpepeKkFr0xfr=xfr=xb9adbaqaaeaacaGaaiaab