НОД (наибольший общий делитель) чисел a и b — это наибольшее положительное число d, которое делит и a, и b без остатка.
Примеры:
- gcd(48, 18) = 6
- gcd(100, 25) = 25
Как вычислять:
- Евклидов алгоритм: gcd(a,b) = gcd(b, a mod b), повторять до остатка 0; последний ненулевой остаток — НОД.
Пример: gcd(48, 18) → 48 mod 18 = 12; gcd(18,12) → 18 mod 12 = 6; gcd(12,6) → 0, значит gcd = 6.
- Есть и факторизационный метод, но он менее эффективен для больших чисел.
Свойства:
- Коммутативность и ассоциативность: gcd(a,b) = gcd(b,a); gcd(a,b,c) = gcd(gcd(a,b), c).
- gcd(a,0) = |a|, gcd(0,0) обычно принимают за 0 (или как неопределённость в некоторых контекстах).
- gcd(a,b) делит любые линейные комбинации ax + by (Беёзут: существуют x,y такие, что ax+by = gcd(a,b)).
Применения:
- Упрощение дробей.
- Решение диофовых уравнений и других задач в теории чисел.
- Связь с НОК: a·b = gcd(a,b) · lcm(a,b) (для ненулевых a,b).
Расширение:
- Можно определить НОД и для нескольких чисел или для полиномов по аналогичным правилам.
Если хотите, могу показать расчёт НОД для ваших конкретных чисел или объяснить алгоритм на примере.
