Что такое алгоритм Евклида?
Алгоритм Евклида — один из древнейших известных алгоритмов: его описал греческий математик Евклид примерно в 300 году до нашей эры. Он позволяет быстро находить наибольший общий делитель (НОД) двух целых чисел — то есть самое большое число, на которое оба делятся без остатка. Этот калькулятор также показывает наименьшее общее кратное (НОК), которое легко выводится прямо из НОД.
Как пользоваться калькулятором
Введите два целых числа в поля выше и нажмите кнопку расчёта. Калькулятор берёт абсолютные значения введённых чисел и многократно применяет правило \(\gcd(a,\,b) = \gcd(b,\,a \bmod b)\), пока остаток не станет равен нулю. После этого он выдаёт сразу и НОД, и НОК.
Разбор формулы
Главная идея в том, что НОД двух чисел не меняется, если большее число заменить на остаток от его деления на меньшее. В символьном виде:
$$\gcd\!\left(a,\,b\right) = \gcd\!\left(b,\,a \bmod b\right)$$Так продолжают до тех пор, пока \(b\) не станет равным 0 — последнее ненулевое значение и есть НОД. После этого НОК вычисляется по формуле
$$\operatorname{lcm}\!\left(a,\,b\right) = \frac{a \times b}{\gcd\!\left(a,\,b\right)}$$ведь произведение двух чисел равно произведению их НОД и НОК.
Пример с решением
Найдём \(\gcd(48,\,36)\): \(48 \bmod 36 = 12\), значит переходим к \(\gcd(36,\,12)\). Далее \(36 \bmod 12 = 0\), поэтому НОД равен 12. НОК тогда равен
$$\frac{48 \times 36}{12} = \frac{1728}{12} = 144$$
Частые вопросы
Что будет, если одно из чисел равно нулю? \(\gcd(a,\,0) = a\). Алгоритм справляется с этим сам собой — цикл сразу останавливается и возвращает ненулевое значение.
Важен ли порядок чисел a и b? Нет. \(\gcd(a,\,b) = \gcd(b,\,a)\); алгоритм автоматически выравнивает порядок на первом же шаге.
Можно ли вводить отрицательные числа? Да. Калькулятор использует абсолютные значения, ведь по общепринятому определению НОД всегда положителен.
