MCD, MCM y el Algoritmo de Euclides

Módulo 5 · Teoría de Números

La baldosa más grande

Van a embaldosar un piso de 252 cm por 105 cm (medidas de ejemplo) con baldosas cuadradas iguales, sin cortar ninguna. ¿Cuál es la baldosa más grande que sirve? Su lado tiene que caber un número exacto de veces en 252 y en 105: es su máximo común divisor.

Euclides explicó cómo encontrarlo sin factorizar, en el libro VII de sus Elementos, hace unos 2.300 años: quitar al número grande el chico tantas veces como se pueda y repetir con lo que sobra. Míralo con cuadrados.

Momento animado

Euclides con cuadrados

Llena el rectángulo con los cuadrados más grandes que quepan y repite con lo que sobra. Mira de qué lado es el último.

Paso del algoritmopaso 1 de 3

Etapas

Etapa 1 de 4 · 252 = 2·105 + 42

En el rectángulo de 252 por 105 caben 2 cuadrados de 105, y sobra una franja de 42 por 105. Todo número que divide a 252 y a 105 divide también a 42 = 252 − 2·105.

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))) — muy rápido. Su versión extendida se usa en la criptografía RSA para calcular la llave privada."

Problemas de Olimpiada

GCD de la Sucesión de Fibonacci

Para los términos de Fibonacci $F_m$ y $F_n$ , ¿cuál es el valor exacto de su máximo común divisor?

Coprimos Consecutivos Cuadráticos

Demuestre cuáles son los únicos valores posibles para $\gcd(n^2 + 1, (n+1)^2 + 1)$ con $n \in \mathbb{Z}^+$ :

Práctica · El algoritmo de Euclides

Con el algoritmo de Euclides, ¿cuál es el MCD de 252 y 105?

Práctica · MCD y MCM

\gcd(252, 105) = 21

, ¿cuál es el MCM de 252 y 105?

Problema de aplicación · Baldosas

Un piso de 252 cm por 105 cm se cubre con baldosas cuadradas iguales, las más grandes posibles, sin cortar ninguna. ¿Cuántas baldosas se usan?

De dónde salen los datos

Euclides: Elementos, libro VII, proposiciones 1 y 2 (traducción inglesa de T. L. Heath, 1908).