TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 51

Anwendung des Euklidischen Algorithmus:

ggT (2007,8367)

8367 =  4 * 2007 + 339 

2007 =  5 *  339 + 312 

 339 =  1 *  312 +  27 

 312 = 11 *   27 +  15 

  27 =  1 *   15 +  12 

  15 =  1 *   12 +   3   <-- ggT 

  12 =  4 *    3 +   0 

ggT(2007,8367) = 3 

Probe:
2007 / 3 = 669
8367 / 3 = 2789