Вычисляйте наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) с пошаговым алгоритмом Евклида.
Наибольший общий делитель (НОД) и Наименьшее общее кратное (НОК) — два важнейших понятия элементарной теории чисел с приложениями от упрощения дробей в средней школе до криптографических алгоритмов, обеспечивающих безопасность интернета.
Алгоритм Евклида, описанный Евклидом около 300 г. до н. э., является одним из старейших и наиболее эффективных алгоритмов в математике. Он вычисляет НОД за O(log(min(a,b))) шагов, быстро завершаясь даже для очень больших чисел. Алгоритм применяет тождество: НОД(a, b) = НОД(b, a mod b) многократно, пока остаток не станет нулевым.
Этот калькулятор показывает полный алгоритм Евклида пошагово для двух чисел, а также вычисляет НОД и НОК для списков нескольких чисел, используя обобщение: НОД(a, b, c) = НОД(НОД(a, b), c).
Найдите НОД(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. НОД = 6. НОК = |48×18|/6 = 864/6 = 144. Проверка: 144/48 = 3 ✓, 144/18 = 8 ✓.
Примените алгоритм Евклида для нахождения НОД(48, 18)
Шаги деления (алгоритм Евклида)
48 = 2 × 18 + 12 → 18 = 1 × 12 + 6 → 12 = 2 × 6 + 0
НОД(48, 18) = последний ненулевой остаток
LCM = |a × b| / GCD
НОК(48, 18)
• НОД(a, b) × НОК(a, b) = |a × b|
• GCD(a, 0) = a (любое число делится само на себя)
• Если НОД(a, b) = 1, то a и b взаимно простые
• Алгоритм Евклида выполняется за время O(log(min(a,b)))
• НОК используется для сложения дробей с разными знаменателями