Вокруг наибольшего общего делителя

Одна из простейших задач, для решения которой понадобится найти наибольший общий делитель пары натуральных чисел a и b, — это задача сокращения дроби a/b.

Напомним, что если числа a и b делятся на одно и то же натуральное число a, то число а называется общим делителем пары чисел a и b. Любая пара натуральных чисел имеет хотя бы один общий делитель (а именно, d = 1), причем любой общий делитель не превосходит каждого из этих чисел. Поэтому среди всех делителей чисел a и b можно выбрать наибольший общий делитель, который обозначается через (a, b), например (20, 100) = 20, (65, 39) = 13. Если (a, b) = 1, то числа a и b называются взаимно простыми. При этом взаимно простые числа a и b совсем не обязательно сами по себе должны быть простыми числами; так, (33, 35) = 1, но 33 = 3 × 11 и 35 = 5 × 7.

У читателя, возможно, сложилось впечатление, что нахождение наибольшего общего делителя пары чисел представляет собой очень простую задачу. Ведь если разложить на простые множители каждое из данных чисел, то сразу станет ясно, как составить из этих простых множителей наибольшее произведение, на которое делятся оба данных числа. Однако все дело в том, что разложить число на простые множители иногда бывает довольно трудно, тогда как нахождение наибольшего общего делителя можно осуществить намного проще — с помощью несложной процедуры. Эта процедура известна уже более 2 тысяч лет и носит название алгоритма Евклида.

Алгоритм Евклида применяется ко многим с виду разнородным объектам. Нахождение наибольшего общего делителя, разложение дроби в цепную дробь, приближение дроби более простыми, решение уравнений в целых числах — вот далеко не полный перечень приложений этого алгоритма.

Источник: Примени математику. И.Н. Сергеев. С.Н. Олехник. С.Б. Гашков. Москва «Наука» 1989.