Вычисляйте наибольший общий делитель (НОД) и наименьшее общее кратное (НОК) с пошаговым алгоритмом Евклида.
Наибольший общий делитель (НОД) и Наименьшее общее кратное (НОК) — два важнейших понятия элементарной теории чисел с приложениями от упрощения дробей в средней школе до криптографических алгоритмов, обеспечивающих безопасность интернета.
Алгоритм Евклида, описанный Евклидом около 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 ✓.