GCD and LCM

O Algoritmo de Euclides — desenvolvido por volta de 300 a.C. e descrito nos Elementos, o tratado de geometria que foi o livro de matemática mais influente da história — é provavelmente o algoritmo mais antigo que ainda usamos sem modificações substanciais. A ideia é elegante: o MDC de dois números é igual ao MDC do menor com o resto da divisão do maior pelo menor. Repita até o resto ser zero. Nenhum computador foi necessário para inventá-lo, mas todo computador moderno o executa. Em 1801, Carl Friedrich Gauss formalizou o Teorema Fundamental da Aritmética no Disquisitiones Arithmeticae: todo inteiro maior que 1 é produto único de fatores primos. É dessa unicidade que emergem o MDC e o MMC como operações naturais — o MDC é o produto dos fatores primos comuns com o menor expoente; o MMC é o produto de todos os fatores com o maior expoente.

MDC e MMC aparecem constantemente em situações que parecem não ter nada a ver com matemática formal. Engenheiros usam o MDC para simplificar razões de engrenagens e relações de transmissão. O ciclo de 52 anos no calendário asteca-maia resulta do MMC entre o ciclo solar de 365 dias e o calendário ritual de 260 dias: MMC(365, 260) = 18.980 dias ≈ 52 anos solares. Em computação, sistemas operacionais de tempo real usam o MMC para calcular o período de hiperframe no escalonamento de tarefas periódicas. Em criptografia, o algoritmo RSA usa o Algoritmo Estendido de Euclides — uma generalização direta do método euclidiano — para calcular inversas modulares, a operação central na geração de chaves.

Para quem programa, o MDC tem suporte nativo em poucas linguagens e o MMC em ainda menos. Python ganhou math.gcd() no Python 3.5 (2015) e math.lcm() apenas no Python 3.9 (2020); JavaScript não tem nenhum dos dois nativo até hoje — Math.gcd simplesmente não existe. A relação MMC(a,b) = (a × b) / MDC(a,b) é a forma eficiente de derivar um a partir do outro. Esta calculadora aceita múltiplos números e entrega os dois resultados ao mesmo tempo, o que poupa bastante tempo quando você está simplificando frações, verificando divisibilidade cruzada, ou tentando descobrir de quanto em quanto tempo dois eventos periódicos voltam a coincidir.

Euclid's algorithm — developed around 300 BC and described in the Elements, the most influential mathematics textbook in history — is arguably the oldest algorithm still used without substantial modification. The idea is elegant: the GCD of two numbers equals the GCD of the smaller with the remainder of dividing the larger by the smaller. Repeat until the remainder is zero. No computer was needed to invent it, yet every modern computer runs it countless times daily. In 1801, Carl Friedrich Gauss formalized the Fundamental Theorem of Arithmetic in Disquisitiones Arithmeticae: every integer greater than 1 is a unique product of prime factors. From that uniqueness, GCD and LCM emerge as natural operations — GCD is the product of common prime factors at their lowest exponents; LCM is the product of all prime factors at their highest exponents.

GCD and LCM show up constantly in situations that seem unrelated to formal mathematics. Engineers use GCD to simplify gear ratios and transmission relationships. The 52-year cycle in the Aztec-Maya calendar results from the LCM of the 365-day solar cycle and the 260-day ritual calendar: LCM(365, 260) = 18,980 days, approximately 52 solar years. In computing, real-time operating systems use LCM to determine the hyperframe period when scheduling periodic tasks. In cryptography, RSA uses the Extended Euclidean Algorithm — a direct generalization of Euclid's method — to compute modular inverses, the central operation in key generation.

For programmers, GCD has native support in few languages and LCM in even fewer. Python gained math.gcd() in Python 3.5 (2015) and math.lcm() only in Python 3.9 (2020); JavaScript has neither native today — Math.gcd simply does not exist. The relationship LCM(a,b) = (a × b) / GCD(a,b) is the efficient way to derive one from the other. This calculator accepts multiple numbers and returns both results at once, saving considerable time when you are simplifying fractions, verifying cross-divisibility, or just trying to figure out how often two periodic events will coincide again.

El algoritmo de Euclides — desarrollado hacia el 300 a.C. y descrito en los Elementos, el tratado de matemáticas más influyente de la historia — es probablemente el algoritmo más antiguo que seguimos usando sin modificaciones sustanciales. La idea es elegante: el MCD de dos números es igual al MCD del menor con el resto de dividir el mayor entre el menor. Se repite hasta que el resto sea cero. No fue necesario ningún ordenador para inventarlo, pero todos los ordenadores modernos lo ejecutan sin parar. En 1801, Carl Friedrich Gauss formalizó el Teorema Fundamental de la Aritmética en Disquisitiones Arithmeticae: todo entero mayor que 1 es producto único de factores primos. De esa unicidad emergen el MCD y el MCM como operaciones naturales — el MCD es el producto de los factores primos comunes con el menor exponente; el MCM es el producto de todos los factores con el mayor exponente.

MCD y MCM aparecen constantemente en situaciones que parecen no tener nada que ver con las matemáticas formales. Los ingenieros usan el MCD para simplificar relaciones de transmisión en engranajes. El ciclo de 52 años en el calendario azteca-maya resulta del MCM entre el ciclo solar de 365 días y el calendario ritual de 260 días: MCM(365, 260) = 18.980 días, aproximadamente 52 años solares. En informática, los sistemas operativos de tiempo real usan el MCM para calcular el período de la hipértrama en la planificación de tareas periódicas. En criptografía, el algoritmo RSA usa el Algoritmo Extendido de Euclides — una generalización directa del método euclidiano — para calcular inversas modulares, la operación central en la generación de claves.

Para quienes programan, el MCD tiene soporte nativo en pocas lenguajes y el MCM en aún menos. Python incorporó math.gcd() en Python 3.5 (2015) y math.lcm() solo en Python 3.9 (2020); JavaScript no tiene ninguno de los dos de forma nativa hoy en día — Math.gcd sencillamente no existe. La relación MCM(a,b) = (a × b) / MCD(a,b) es la forma eficiente de obtener uno a partir del otro. Esta calculadora acepta varios números y devuelve ambos resultados a la vez, lo que ahorra bastante tiempo cuando se simplifican fracciones, se verifica divisibilidad cruzada, o simplemente se intenta averiguar cada cuánto tiempo dos eventos periódicos vuelven a coincidir.