Чтобы найти наибольший общий делитель (НОД, gcd) двух чисел, используем простой и наглядный метод — Евклидов алгоритм.
Что такое НОД
- НОД(a, b) — наибольшее положительное число, которое делит оба числа без остатка.
- Для двух чисел можно использовать деление с остатком: gcd(a, b) = gcd(b, a mod b), повторяем, пока остаток не станет 0. Последний делитель — ответ.
- Для более чем двух чисел: gcd(a, b, c) = gcd(gcd(a, b), c).
Пошаговый алгоритм (Евклид)
1) Пусть a и b — целые числа. Если b = 0, тогда gcd(a, 0) = |a| и работа завершена.
2) Иначе заменяем пару (a, b) на (b, a mod b) и повторяем шаг 1.
3) Когда остаток станет 0, последний ненулевой делитель — это gcd.
Пример 1: gcd(48, 180)
- 180 mod 48 = 180 - 3*48 = 180 - 144 = 36
- Теперь gcd(48, 36)
- 48 mod 36 = 12
- Теперь gcd(36, 12)
- 36 mod 12 = 0
- Ответ: gcd = 12
Пример 2: gcd(101, 103)
- 103 mod 101 = 2
- gcd(101, 2)
- 101 mod 2 = 1
- gcd(2, 1)
- 2 mod 1 = 0
- Ответ: gcd = 1
Особые случаи
- gcd(0, n) = |n| (если n ≠ 0)
- gcd(0, 0) обычно трактуют как 0 или не определён, но в большинстве задач принимают gcd(0,0) = 0.
Если нужно, могу показать решение для конкретных чисел или для трёх и более чисел (например, gcd(60, 84, 126) = gcd(gcd(60, 84), 126)). Пришлите числа, и я дам пошаговое решение.
