Największy Wspólny Dzielnik

Największym wspólnym dzielnikiem dwóch liczb naturalnych a, b nazywamy najwiekszą liczbę naturalną k taką, że (k|a) oraz (k|b). Oznaczamy ją NWD(a,b). Oto najważnieje własności tej funkcji:

1. NWD(a,b) = NWD(b,a)
2. Jeśli a|b to NWD(a,b) = a
3. Jeśli a = k b + r, to NWD(a,b) = NWD(b,r)

FUNCTION NWD(a,b)
BEGIN
  WHILE (b <> 0) DO
    [a,b] := [b, a mod b]
  OD
  RETURN a;
END

function NWD(a,b){
  var q;
  while (b != 0){
    q = a;
    a = b;
    b = q mod b;
 }
 return a;
}