euclides

invoer: $a,b\in\NN$ met $a>b>0$

uitvoer: $g\in\ZZ$

claim: $g=\ggd(a,b)$

  • 1   $r\leftarrow a\bmod b$
  • 2   zolang $r\not=0$
    • 2.1   $a\leftarrow b$
    • 2.2   $b\leftarrow r$
    • 2.3   $r\leftarrow a\bmod b$
  • 3   $g\leftarrow b$
$a={}$
$b={}$