Máximo común divisor

Es el mayor número entero positivo que divide a ambos sin dejar resto. En español se abrevia MCD y en los textos en inglés aparece como GCD, GCF o HCF: se trata del mismo valor. Para 12 y 16 es 4.

Descomponga los dos números en factores primos y multiplique los que aparecen en ambas descomposiciones, tantas veces como estén en las dos. 12 = 2 × 2 × 3 y 16 = 2 × 2 × 2 × 2 comparten 2 × 2, de modo que el MCD es 4.

Euclides lo describió en los Elementos hacia el año 300 a. C.: se divide el número mayor entre el menor y se sustituye la pareja por el menor y el resto, hasta que el resto sea 0. Con 16 y 12: 16 entre 12 deja resto 4 y 12 entre 4 deja resto 0, luego el MCD es 4. Nunca hay que factorizar, y por eso el método sigue siendo rápido con números imposibles de descomponer.