Módulos / tdn-1 / Capítulo 1 — Divisibilidad y MCD / Lección 1.1

El algoritmo de Euclides: la máquina del MCD

Lección 1.1·Capítulo 1 — Divisibilidad y MCD·7 min·Piloto
▶

Video en producción

El contenido pedagógico de esta lección ya está completo y lo puedes leer abajo. El video con la voz de Eduardo Espinoza Ramos se produce según la Política de IA.

Disclosure de IA: al publicarse, este contenido reproducirá digitalmente, con autorización expresa del autor, la voz y fisonomía de Eduardo Espinoza Ramos. Curaduría revisada por matemáticos profesionales. Política completa →

Objetivo de la lección

Dominar el algoritmo de Euclides para calcular el MCD, entender la identidad de Bézout, y usarlos para resolver problemas elementales de teoría de números olímpica.

El problema de la moneda

Tienes monedas de 15 soles y de 21 soles. ¿Qué cantidades exactas de dinero puedes representar sumando y restando estas monedas? La respuesta es: todos los múltiplos de gcd⁡(15,21)=3\gcd(15,21) = 3. ¿Por qué? Porque 3=3⋅15−2⋅213 = 3\cdot 15 - 2\cdot 21.

Esta observación — que el MCD de dos números es combinación lineal entera de ellos — es uno de los hechos más útiles de toda la teoría de números elemental. Se llama identidad de Bézout y el algoritmo de Euclides es la herramienta para encontrarla.

Si compites en olimpiadas de matemáticas, necesitas este algoritmo en el punto de los reflejos. Hoy lo automatizamos.

El algoritmo paso a paso

El algoritmo de Euclides se basa en la siguiente observación clave: si a=bq+ra = bq + r con 0≤r<b0 \le r < b, entonces gcd⁡(a,b)=gcd⁡(b,r)\gcd(a,b) = \gcd(b,r).

Por qué funciona: todo divisor común de aa y bb también divide a r=a−bqr = a - bq, y viceversa. Así el conjunto de divisores comunes no cambia al reemplazar (a,b)(a,b) por (b,r)(b,r).

Ejemplo: gcd⁡(252,105)\gcd(252, 105). Dividimos: 252=2⋅105+42252 = 2\cdot105 + 42, luego 105=2⋅42+21105 = 2\cdot42+21, luego 42=2⋅21+042 = 2\cdot21+0. Como llegamos al resto 00, el MCD es el último resto no nulo: gcd⁡(252,105)=21\gcd(252,105)=21.

gcd⁡(a,b)=gcd⁡(b,  a mod b)\gcd(a,b) = \gcd(b,\; a \bmod b)

La identidad de Bézout

El algoritmo de Euclides hace más que calcular el MCD. Corrido hacia atrás —el llamado algoritmo extendido— nos da enteros xx, yy tales que ax+by=gcd⁡(a,b)ax+by = \gcd(a,b).

Continuando el ejemplo: de 21=105−2⋅42=105−2(252−2⋅105)=5⋅105−2⋅25221 = 105 - 2\cdot42 = 105 - 2(252-2\cdot105) = 5\cdot105 - 2\cdot252. Así 21=(−2)⋅252+5⋅10521 = (-2)\cdot252 + 5\cdot105.

Identidad de Bézout: para todo par de enteros aa, bb (no ambos cero), existen enteros xx, yy con ax+by=gcd⁡(a,b)ax + by = \gcd(a,b). Consecuencia inmediata: gcd⁡(a,b)=1\gcd(a,b)=1 si y solo si existen x,yx,y con ax+by=1ax+by=1.

ax+by=gcd⁡(a,b) tiene solucioˊn entera (x,y)ax + by = \gcd(a,b) \text{ tiene solución entera } (x,y)

Las dos herramientas más usadas en olimpiadas

De Bézout salen dos resultados que debes conocer: Lema de Euclides (si gcd⁡(a,n)=1\gcd(a,n)=1 y n∣abn\mid ab, entonces n∣bn\mid b) y el resultado de que gcd⁡(a,b)=1\gcd(a,b)=1 es equivalente a que aa y bb no comparten factores primos.

En la próxima lección veremos la identidad de Bézout construida explícitamente con el algoritmo extendido. Después vendrán los primos y el Teorema Fundamental de la Aritmética.

Practica los problemas de abajo. El objetivo es que en un concurso calcules el MCD de dos números de 3 cifras en menos de un minuto.

Problemas del Capítulo 1 — con solución

6 problemas verificados. Intenta cada uno antes de abrir la solución.

1.1★

Calcula gcd⁡(48,36)\gcd(48,36) usando el algoritmo de Euclides.

1.2★

Calcula gcd⁡(391,299)\gcd(391,299).

1.3★★

Halla enteros x,yx,y tales que 17x+13y=117x+13y=1.

1.4★★

Prueba que si d=gcd⁡(a,b)d=\gcd(a,b) entonces gcd⁡(a/d,b/d)=1\gcd(a/d,b/d)=1.

1.5★★★ONEM (clásico)

Prueba que para todo entero nn, gcd⁡(n2+1,n+1)\gcd(n^2+1, n+1) divide a 2.

1.6★★★

Halla todos los enteros nn tales que n∣2n+3n\mid 2n+3.

← Volver al móduloLección 1.2 →