Največji skupni delitelj

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Nàjvéčji skúpni delítelj (tudi nàjvéčja skúpna méra) celih števil je v matematiki največji od deliteljev, ki so skupni številoma. Kot funkcijo se ga po navadi označuje z D (n, k)\, . V tuji literaturi ga označujejo z \operatorname{GCD} (n, k)\, ali z \gcd (n, k)\, , kot okrajšavo za angleški izraz greatest common divisor.

Zgled:

  • število 28 ima delitelje 1, 2, 4, 7, 14, 28
  • število 24 ima delitelje 1, 2, 3, 4, 6, 12, 24
  • skupni delitelji so 1, 2, 4
  • največji skupni delitelj je 4, in se zapiše D (24, 28) = 4\, .

V najslabšem primeru imata števili samo enega delitelja 1 (D (n, k) = 1\, ) in v tem primeru sta števili tuji.

Obstaja več metod za določanje največjega skupnega delitelja, najbolj znani sta metoda s pomočjo razcepa na praštevila in Evklidov algoritem.


Programsko se lahko izračuna največji skupni delitelj dveh števil z uporabo funkcij MOD in DIV v paskalu

x := 28; // stevilo a
y := 24; // stevilo b

dmax := 1;
for i:=1 to x do begin
   if ((x mod i) = 0 AND ((y mod i) =0) then dmax:= i;
end;
writeln(dmax); //izpiše 4