Μέγιστος Κοινός Διαιρέτης gcd(a, b) των αριθμών a, b

Ευκλείδιος Αλγόριθμος

function gcd(a, b)
while b ≠ 0
if a > b

a := a - b

else

b := b - a

return a

Mathematica

EuclideanAlgorithm[p_Integer, q_Integer] := Module[{a, b}, If[p == 0,

If[q == 0, Return[Infinity]];

Return[Abs[q]]];

a = Abs[p]; b = Abs[q];

While[a > 0, {a, b} = {Mod[b, a], a}];

b]

s = EuclideanAlgorithm[1554851, 155485782317];

s = gcd(1554851, 155485782317) = 37

Mathematica συνάρτηση : GCD(a ,b)

Αν gcd(a, b) =1, τότε οι a, b αποκαλούνται σχετικά πρώτοι