El algoritmo de Euclides con 1071 y 465 llega al mcd 3 pasando por los restos 141, 42, 15, 12

Toma restos hasta que uno sea cero; el último resto no nulo es el máximo común divisor.

Ecuaciones y álgebra · Nivel: Resultado clásico · Actualizado el 2026-11-10

1071 mod 465 es 141. 465 mod 141 es 42. 141 mod 42 es 15, 42 mod 15 es 12, 15 mod 12 es 3, y 12 mod 3 es 0. El último resto no nulo, 3, es el máximo común divisor, y cada paso es legítimo por la misma razón: cualquier número que divida a la vez a a y a b también divide a − qb, así que el par y su resto tienen exactamente los mismos divisores. Aquí no hace falta factorizar nada, y ese es el punto práctico: 3 es la respuesta mucho antes de que nadie sepa por qué 1071 es 3·357.

El número de pasos es lo que hay que vigilar. Lamé demostró en 1844 que el algoritmo de Euclides sobre un par de enteros nunca tarda más de unas cinco veces el número de dígitos decimales del menor, y que los peores casos son números de Fibonacci consecutivos; por eso 141, 42, 15, 12, 3 en esta página se encogen rápido: aquí nada es vecino de Fibonacci. La versión extendida de la misma tabla de restos también devuelve coeficientes con 3 = 1071s + 465t, el ingrediente de toda rutina de división modular en un sistema de álgebra computacional.

Respuesta

3

Cómo leerla

15 mod 12, el último resto no nulo. Los dos primeros enlaces son los pasos iniciales, 1071 mod 465 = 141 y 465 mod 141 = 42.

Fuente

Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give

Resuélvelo en la calculadora

Estos enlaces abren la calculadora adecuada con los números de este problema ya escritos. La línea de arriba es lo que debería mostrar la pantalla: compruébalo tú mismo.

Este es un sitio de herramientas independiente de terceros. No está afiliado a Casio, Texas Instruments ni sus distribuidores, ni cuenta con su patrocinio o autorización. Los nombres de modelos y productos son marcas comerciales de sus respectivos titulares y se incluyen aquí únicamente para identificar los dispositivos.

Las secuencias de teclas de estos manuales se redactaron a partir de los propios datos de disposición de este sitio —los mismos que representa la calculadora en línea— junto con información de producto disponible públicamente. Las especificaciones y las configuraciones regionales se verifican con el dispositivo físico y con el material más reciente del fabricante.