Калькулятор НОД по алгоритму Евклида

Введите расчет

Число 1

Число 2

Результатов

https://example.com

Наибольший общий делитель

4

НОД (он же GCF/GCD)

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

Что такое алгоритм Евклида?

Наибольший общий делитель (НОД), известный в английских источниках как GCF (greatest common factor) или GCD (greatest common divisor), — это самое большое целое число, на которое без остатка делятся оба заданных числа. Алгоритм Евклида — древний и удивительно эффективный способ его найти с помощью последовательного деления с остатком. Этот калькулятор вычисляет НОД любых двух целых чисел и показывает каждый шаг деления, чтобы вы могли проследить весь ход решения.

Алгоритм Евклида замощает прямоугольник наибольшими равными квадратами — сторона такого квадрата и есть НОД.

Как пользоваться калькулятором

Введите два целых числа в поля Число 1 и Число 2. Калькулятор берёт большее число как делимое, а меньшее как делитель и делит их по кругу, пока остаток не станет равен нулю. Последний ненулевой делитель и есть искомый НОД. Порядок чисел не важен, а знак «минус» не учитывается, поскольку НОД зависит только от модуля чисел.

Разбор формулы

На каждом шаге вычисляются неполное частное и остаток: \(a = c \times b + R\), где \(c = \lfloor a / b \rfloor\) (целая часть деления), а \(R = a \bmod b\) (остаток). Затем \(a\) заменяется на \(b\), а \(b\) — на \(R\), и шаг повторяется. Поскольку каждый новый остаток строго меньше предыдущего делителя, процесс рано или поздно завершится. Как только \(R = 0\), текущий делитель и будет ответом. В виде рекурсии это записывается так: $$\gcd(a, b) = \gcd(b,\ a \bmod b),\quad \gcd(a, 0) = a$$

Реклама

Пример с решением

Найдём НОД(816, 2260). Примем \(a = 2260\), \(b = 816\).

$$2260 = 2 \times 816 + 628$$ $$816 = 1 \times 628 + 188$$ $$628 = 3 \times 188 + 64$$ $$188 = 2 \times 64 + 60$$ $$64 = 1 \times 60 + 4$$ $$60 = 15 \times 4 + 0$$ Остаток обнуляется при делителе 4, значит НОД(816, 2260) = 4.

На каждом шаге \((a, b)\) заменяется на \((b,\ a \bmod b)\), пока остаток не станет 0; последний ненулевой делитель — это НОД.

Частые вопросы

НОД, GCF и GCD — это одно и то же? Да. «Наибольший общий делитель», «greatest common factor» и «greatest common divisor» — синонимы; этот калькулятор отвечает на любой из этих запросов.

Что будет, если одно из чисел равно 0? \(\gcd(a, 0) = a\), ведь на ноль делится любое число. Если же оба числа равны нулю, НОД не определён.

Можно ли найти НОД трёх чисел? Да, применяйте калькулятор попарно: $$\gcd(x, y, z) = \gcd(\gcd(x, y),\ z)$$