MCD, MCM y el Algoritmo de Euclides

Modulo 5 · Teoría de Números

MCD y MCM: Definiciones

El Máximo Común Divisor ( $\gcd(a, b)$ ) es el mayor entero positivo que divide a ambos $a$ y $b$ .

El Mínimo Común Múltiplo ( $\text{lcm}(a, b)$ ) es el menor entero positivo que es múltiplo de ambos.

🔗 Relación Fundamental

\gcd(a,b) \times \text{lcm}(a,b) = |a \times b|

Esta identidad permite calcular el MCM a partir del MCD (que es más fácil de obtener con Euclides).

Dos números son coprimos (o primos relativos) si $\gcd(a,b) = 1$ . Esto NO significa que sean primos individualmente.

✓ Coprimos

$\gcd(8, 15) = 1$
$\gcd(9, 14) = 1$
$\gcd(n, n+1) = 1$ siempre

✗ No coprimos

$\gcd(12, 18) = 6$
$\gcd(100, 75) = 25$

Concepto Clave

"Dos números consecutivos siempre son coprimos: gcd(n, n+1) = 1. Este hecho inocente resuelve muchos problemas de olimpiada."

El Algoritmo de Euclides

Euclides descubrió que $\gcd(a, b) = \gcd(b, a \bmod b)$ . Al aplicar esto repetidamente, llegamos al MCD sin necesidad de factorizar.

Algoritmo de Euclides — Simulador

Número

a

Número

b

252 = 105 \times 2 + 42

105 = 42 \times 2 + 21

42 = 21 \times 2 + 0

¡Residuo 0!

MCD

$21$

$\gcd(252, 105) = 21$

MCM

$1260$

$\text{lcm}(252, 105) = 1260$

¿Por qué funciona?

Partimos de

a = bq + r

Si d | a y d | b, entonces

d \mid (a - bq) = r

Así, los divisores comunes de (a,b) son los mismos que los de (b,r)

\gcd(a,b) = \gcd(b,r)

Cuando r = 0, el último divisor no nulo es el MCD

\gcd(a, 0) = a

Concepto Clave

"El algoritmo de Euclides es O(log(min(a,b))) — increíblemente rápido. Es la base de la criptografía RSA moderna."

Problemas de Olimpiada

Problema 1

GCD de Fibonacci

Demuestre que $\gcd(F_m, F_n) = F_{\gcd(m,n)}$ , donde $F_k$ es el k-ésimo número de Fibonacci.

Ver Pista

Pista 1: Prueba primero que $F_m \mid F_{mk}$ para todo entero $k$ .

Pista 2: Usa que $\gcd(F_m, F_n) = \gcd(F_m, F_{n \bmod m})$ (análogo a Euclides).

Pista 3: Prueba que $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$ .

Problema 2

Coprimos Consecutivos

Demuestre que $\gcd(n^2 + 1, (n+1)^2 + 1) \in \{1, 5\}$ .

Ver Solución

Sea $d = \gcd(n^2+1, (n+1)^2+1)$ .

Entonces $d \mid ((n+1)^2 + 1 - (n^2+1)) = 2n + 1$ .

Y $d \mid (n^2+1)$ . Así $d \mid (4(n^2+1) - (2n+1)^2) = 4 - 4n^2 - 1 + 4n^2 + 4n + 1$

Simplificando: $d \mid (4n^2 + 4 - 4n^2 - 4n - 1) = 3 - 4n$ ... mejor:

$d \mid 4(n^2+1) = 4n^2 + 4$ y $d \mid (2n+1)^2 = 4n^2 + 4n + 1$ .

Entonces $d \mid (4n + 1 - 4) = 4n - 3$ y $d \mid (2n+1)$ .

Así $d \mid (2(2n+1) - (4n-3)) = 5$ .

d \mid 5

, así que

d \in \{1, 5\}

. ∎