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

Евклид

Одна из простейших задач, для решения которой понадобится найти наибольший общий делитель пары натуральных чисел 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.

Похожие записи

Делимость чисел Из всех действий арифметики самое своенравное — это деление. Оно обладает особыми свойствами, можно сказать, особым «нравом». Возьмем хотя бы обра...
Замечательные свойства «девяти»... Интересные свойства числа 9 часто применяются в арифметике как для теоретических изысканий и практических действий, так и для составления различных ...
Индийская поместная нумерация... В различных областях Индии существовали разнообразные системы нумерации. Одна из них распространилась по всему миру и в настоящее время является общ...
О числах 37 и 41 Число 37 обладает многими любопытными свойствами. Так, умноженное на 3 и на числа, кратные 3 (до 27 включительно), оно дает произведения, изображаемые...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *