Recurrencias y aritmética · Definición

Máximo común divisor

matemáticas discretasteoría de números

Antes de empezar necesitas conocer

Mide cuánta estructura multiplicativa comparten dos enteros y permite simplificar fracciones y resolver ecuaciones con enteros.

Definición

El máximo común divisor \(\gcd(a,b)\) de dos enteros \(a\) y \(b\), no ambos nulos, es el mayor entero que divide a los dos.

\[\gcd(a,b)=\max\{d\in\mathbb{Z}:\ d\mid a,\ d\mid b\}\]

Para hallarlo se listan los divisores comunes o, mejor, se factoriza: se toman los primos presentes en ambos números con el menor exponente. Así \(48=2^4\cdot3\) y \(180=2^2\cdot3^2\cdot5\) dan \(\gcd(48,180)=2^2\cdot3=12\). Dos enteros con \(\gcd(a,b)=1\) se llaman coprimos, como 35 y 64, aunque ninguno sea primo.

Algunas propiedades se usan constantemente: \(\gcd(a,0)=|a|\), \(\gcd(a,b)=\gcd(b,a)\) y \(\gcd(a,b)=\gcd(a-qb,\,b)\) para cualquier entero \(q\). Esta última afirma que restar múltiplos de un número al otro no cambia los divisores comunes, y es el motor del algoritmo de Euclides. Además, si \(d=\gcd(a,b)\), entonces \(a/d\) y \(b/d\) son coprimos, de ahí que una fracción se reduzca dividiendo numerador y denominador entre su máximo común divisor.

El máximo común divisor es también el menor entero positivo de la forma \(ma+nb\) con \(m,n\) enteros (identidad de Bézout), lo que garantiza que \(ax+by=c\) tenga soluciones enteras exactamente cuando \(\gcd(a,b)\mid c\). Se relaciona con el mínimo común múltiplo mediante \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|\). Un error típico es confundirlos: el máximo común divisor es siempre menor o igual que ambos números; el mínimo común múltiplo, mayor o igual.

Para pensar

¿Por qué \(\gcd(a,b)=\gcd(a-b,\,b)\)?

Todo divisor común de \(a\) y \(b\) divide a \(a-b\); y todo divisor común de \(a-b\) y \(b\) divide a \((a-b)+b=a\). Los dos pares tienen los mismos divisores comunes.

Si \(\gcd(a,b)=6\) y \(\operatorname{lcm}(a,b)=60\), ¿cuánto vale \(|ab|\)?

\(|ab|=\gcd\cdot\operatorname{lcm}=6\cdot60=360\).

Ejercicios 10

  1. Calcula \(\gcd(12,18)\).
  2. Calcula \(\gcd(35,64)\).
  3. Calcula \(\gcd(0,9)\).
  4. Calcula \(\gcd(48,180)\).
  5. Calcula \(\gcd(84,126)\).
  6. Calcula \(\gcd(1023,63)\), es decir, \(\gcd(2^{10}-1,\,2^{6}-1)\).
  7. ¿Para cuál valor de \(b\) se cumple \(\gcd(20,b)=4\)?
  8. Si \(d=\gcd(a,b)\) con \(a,b\) no nulos, ¿cuánto vale \(\gcd(a/d,\,b/d)\)?
  9. ¿Cuántos enteros \(n\) con \(1\le n\le100\) cumplen \(\gcd(n,100)=1\)?
  10. Si \(\gcd(a,b)=1\), ¿qué valores puede tomar \(\gcd(a+b,\,a-b)\) para \(a\ne b\)?

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §4.3
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §4.4
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §4.8