Největší společný dělitel celých čísel

• pro dvě celá čísla a, b , pro která platí $a \geq b$, definujeme jejich podíl quot(a,b) a zbytek po dělení rem(a,b) jako celá čísla, pro která platí
  
  a = quot(a,b) b + rem(a,b)
  
  

• přitom 0 <= rem(a,b) < b

• označíme-li největší společný dělitel čísel a, b jako gcd(a,b) , potom pokud rem(a,b) je nenulové platí
  
  gcd(a,b) = gcd(b,rem(a,b))
  
  

• gcd(a,b) totiž dělí jak a tak b , dělí také b quot(a,b) a musí tedy dělit i rem(a,b)

• na této identitě je založen Euklidův algoritmus pro výpočet největšího společného dělitele

• Euklidův algoritmus pro výpočet největšího společného dělitele dvou celých čísel

• Algoritmus

        gcd:=GCDI(a,b)
          [a, b jsou celá čísla
           použité algoritmy:
             rem(a,b) - zbytek po dělení čísla a číslem b ]
        1. if  a  <  b  then
               r:=a;
               a:=b;
               b:=r;
            fi
        2. while not(b=0) do
             r:=rem(a,b);
             a:=b;
             b:=r;
           do
        3. gcd:=a;