Наибольший общий делитель
Наибольший общий делитель как максимальное число, делящее два данных числа
Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей. Пример: для чисел 70 и 105 наибольший общий делитель равен 35.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
Возможные обозначения наибольшего общего делителя чисел m и n:
- НОД(m, n)
- (m, n)
- gcd(m, n) (от англ. Greatest Common Divisor)
Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.
Алгоритм Евклида
Стандартный алгоритм Евклида
Пусть
и — целые числа, не равные одновременно нулю, и последовательность чиселопределена тем, что каждое
— это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то естьТогда НОД(a,b), наибольший общий делитель
и , равен , последнему ненулевому члену этой последовательности.Существование таких
, то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией по m.Корректность этого алгоритма вытекает из следующих двух утверждений:
- Пусть , тогда
- Пусть k — любой общий делитель чисел a и b, не обязательно максимальный, тогда ; где и — целые числа из определения.
- Тогда k также общий делитель чисел b и r, так как b делится на k по определению, а (выражение в скобках есть целое число, следовательно, k делит r без остатка)
- Обратное также верно и доказывается аналогично 2) - любой делитель b и r так же является делителем a и b.
- Следовательно, все общие делители пар чисел a,b и b,r совпадают. Другими словами, нет общего делителя у чисел a,b, который не был бы также делителем b,r, и наоборот.
- В частности, максимальный делитель остается тем же самым. Что и требовалось доказать.
- для любого ненулевого
Проще сформулировать алгоритм Евклида так: если даны натуральные числа
и и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.Расширенный алгоритм Евклида
Формулы для
могут быть переписаны следующим образом:здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
Связь с цепными дробями
Отношение
допускает представление в виде цепной дроби:- .
При этом цепная дробь без последнего члена равна отношению коэффициентов Безу
, взятому со знаком минус:- .