Наибольший общий делитель
Версия от 15:06, 30 июня 2010; Mamoshkin.Arseny (обсуждение | вклад)
Эта статья находится в разработке!
Наибольший общий делитель как максимальное число, делящее два данных числа
Алгоритм Евклида
Стандартный алгоритм Евклида
Пусть
и — целые числа, не равные одновременно нулю, и последовательность чиселопределена тем, что каждое
— это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то естьТогда НОД(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 — коэффициентами Безу. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.
Связь с цепными дробями
Отношение
допускает представление в виде цепной дроби:- .
При этом цепная дробь без последнего члена равна отношению коэффициентов Безу
, взятому со знаком минус:- .