Mapa mental: Algoritmo de Euclides para hallar el MCD

Explorar

Mapa mental: Algoritmo de Euclides para hallar el MCD · Formatom

Algoritmo de Euclides para hallar el MCD

Contenido del mapa

Algoritmo de Euclides — Receta de divisiones seguidas para hallar el MCD sin factorizar.
- ¿Qué es? — Método para hallar el MCD solo con divisiones y restos.
  - Sin factorizar — No necesitas descomponer en primos, solo dividir.
  - Solo usa restos — En cada división te quedas con el resto para seguir.
  - Termina en resto 0 — Cuando el resto es 0, el último divisor es el MCD.
- Palabras clave — Vocabulario mínimo para aplicar el algoritmo.
  - División: a = bq + r — a es dividendo, b divisor, q cociente y r resto.
  - Resto r — Es lo que sobra y siempre cumple 0 ≤ r < b.
  - MCD — El número más grande que divide a los dos a la vez.
  - Algoritmo — Receta de pasos cortos que repites igual cada vez.
- Idea clave — MCD(a,b) = MCD(b,r) donde r es el resto.
  - Mismos divisores — Todo divisor común de a y b también divide a r, y viceversa.
  - Números se achican — Como r es menor que b, la pareja se hace pequeña y termina.
  - Analogía de la cinta — Como cortar cintas de 48 y 18 cm en trozos iguales sin desperdicio.
- Pasos del algoritmo — Repite dividir y cambiar de pareja hasta resto 0.
  - 1. Divide a entre b — Con a mayor que b, calcula a = bq + r.
  - 2. Si r = 0, para — El MCD es b, el último divisor usado.
  - 3. Si r ≠ 0, repite — Olvida el a viejo y sigue con la nueva pareja (b,r).
  - Cadena hasta 0 — Sigues a → b → r1 → r2 → … → 0.
- Ejemplo: MCD(1071,462) — Modelo resuelto en 3 divisiones que da MCD = 21.
  - Paso 1: 1071 ÷ 462 — 1071 = 462·2 + 147. Sigue con (462,147).
  - Paso 2: 462 ÷ 147 — 462 = 147·3 + 21. Sigue con (147,21).
  - Paso 3: 147 ÷ 21 — 147 = 21·7 + 0. Resto 0, el MCD es 21.

El Algoritmo de Euclides sirve para encontrar el Máximo Común Divisor de dos números sin factorizar. Solo se hacen divisiones seguidas y te quedas con los restos. Cuando llegas a resto 0, el último divisor usado es el MCD.

Su base es la regla MCD(a,b) = MCD(b,r), donde r es el resto de dividir a entre b. Esto funciona porque todo divisor común de a y b también divide al resto r, y al revés también. Entonces la pareja (a,b) y la pareja (b,r) tienen los mismos divisores comunes y el mismo MCD, pero con números más pequeños.

Para aplicarlo con a mayor que b, divides a entre b y obtienes cociente q y resto r con la forma a = bq + r. Si r es 0, terminas y el MCD es b. Si r no es 0, olvidas el a viejo y repites con la nueva pareja (b,r). Como el resto siempre cumple 0 ≤ r < b, los números se achican rápido y el proceso siempre termina en la cadena a → b → r1 → r2 → … → 0.

Un ejemplo modelo es MCD(1071,462). Primero 1071 = 462·2 + 147, luego 462 = 147·3 + 21 y finalmente 147 = 21·7 + 0. Al llegar a resto 0 se para y se concluye que el MCD es 21, que divide a ambos y es el mayor divisor común posible.