MCD(98, 12) = x
ovviamente 1< x <= min(98, 12)
s = 98+12= 110 = 5*11*2
divisori non banali di s sono 5, 11, 2, 5*11, 5*2, 11*2
x = 5, 11, 2 , ....
5 non divide 98, 12 e quindi nemmeno i multipli di 5
11 non divide 98, 12 e quindi nemmeno i multipli di 11
2 divide 98, 12
allora il MCD(98, 12) = 2
analogamente nei casi più complessi
MCD(a, b) = x
s = a+b allora x deve dividere s.
ALGORITMO PIU' VELOCE:
a > b MCD(a,b) = x , se a = c mod b allora x è un divisore di c con c diverso da zero
se c = 0 allora MCD(a, b ) = b
MCD(98, 12)= x
98 mod 12 = 2 diverso da 0 allora il MCD(98, 12) deve essere 2 o un suo divisore quindi 2
se il modulo fosse stato zero allora il MCD tra i due numeri sarebbe stato il più piccolo tra i due