El máximo común divisor de un conjunto de número enteros $\{ a_1, a_2, \dots, a_n \}$ es el entero positivo más grande que divide (exactamente) a cada uno de los enteros del conjunto.
Por ejemplo, el máximo común divisor de ${12,18, -24}$ es 6. Para verlo, estudiemos la siguiente tabla: en ella se han puesto todos los divisores de cada número, y se han marcado en negritas aquellos divisores que son comunes a los tres números. Como se puede observar, el más grande de éstos es 6.
| Número | Divisores |
|---|---|
| 12 | 1, 2, 3, 4, 6, 12 |
| 18 | 1, 2, 3, 6, 9, 18 |
| -24 |
1, 2, 3, 4, 6, 8, 12, 24 |
El máximo común divisor de dos número $a$ y $b$ se acostumbra denotar con el símbolo $MCD(a,b)$ o bien sólo $(a,b)$.
Una definición más formal es:
Dados dos enteros $a$ y $b$, no ambos cero, definimos el máximo común divisor como el entero $d$ que satisface:
- $d|a$ y $d|b$
- Si $h|a$ y $h|b$ entonces $h \leq d$
En esta definición hay que notar, que la condición "no ambos cero" es sólo para garantizar la existencia del máximo común divisor, pues de lo contrario, todo número sería divisor común de cero y cero. Luego, la primera condición sobre $d$ es equivalente a pedir que $d$ sea divisor común de $a$ y $b$, y la segunda condición sólo significa que $d$ es el máximo.
El algoritmo más rápido para calcular el máximo común divisor, es el algoritmo de Euclides [1]. El proceso mediante el cálculo de los divisores comunes es demasiado lento.
Una de las propiedades más importantes del máximo común divisor está dada por la Identidad de Bezout [2]:
Dados dos enteros positivos $a$ y $b$, no ambos cero, existen enteros $x_0$ y $y_0$ tales que: $$(a,b) = ax_0 +by_0$$