MDC - Maior Divisor Comum (ou GCD)

Number Theory - Euclid Algorithm
Wiki - GCD

Propriedades

  1. Distributiva: gcd(ma,mb,mc) = m gcd(a,b,c)
  2. Associativa: gcd(a,b,c) = gcd(gcd(a,b),c) = gcd(a,gcd(b,c))
  3. Idempotente: gcd(a,a) = a
  4. Comutativa: gcd(a,b) = gcd(b,a)
  5. gcd(a + mb, b) = gcd(a, b)
  6. gcd(a/m, b/m) = gcd(a, b)/m
  7. se a1 e a2 são primos relativos (gcd(a1,a2)=1), then gcd(a1·a2, b) = gcd(a1, b)·gcd(a2, b).
    Portanto, gcd(a, b·c) = 1 sse gcd(a, b) = 1 /\ gcd(a, c) = 1