Наибольший общий делитель. Алгоритм Евклида

Если d делит а и d делит b, то d - общий делитель чисел а и b. Так как делителей чисел а и b конечное число, то и общих делителей чисел а и b конечное число. Среди любого конечного числа целых чисел существует наибольшее. Наибольший из общих делителей называется наибольшим общим делителем чисел а и b и обозначается НОД или просто Аналогично вводится наибольший делитель нескольких целых чисел Если наибольший общий делитель чисел равен 1, то эти числа называются взаимно простыми. Числа попарно взаимно простые являются и взаимно простыми, но числа взаимно простые не обязательно попарно взаимно простые. Например, числа 10, 12, 27 взаимно простые, но пары 10 и 12, 12 и 27 имеют общие множители.

Алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел. Пусть а и b – положительные целые числа и Применим теорему о делении с остатком несколько раз:

............

Процесс деления предыдущего остатка на следующий конечен, так как в последовательности:

может быть только конечное число чисел (не более, чем b чисел).

Пусть х – общий делитель чисел а и b. Тогда двигаясь от равенства к следующему, начиная с первого, получим делится на х, делится на х и т.д., делится на х. Двигаясь же от последнего равенства к первому, заметим, что делится на делится на и т.д., b делится на , а делится на . Таким образом, - общий делитель чисел а и b, делящийся на любой другой общий делитель этих чисел, т.е. Таким образом, последний ненулевой остаток в алгоритме Евклида – наибольший общий делитель.

Пример. Найти НОД(1173, 323).

Решение:

Ответ: 17.