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

Евклид

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

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

Упрощение признака делимости на 8... В школе обычно сообщают такой признак делимости на 8: если число, которое составляют последние три цифры данного числа, делится на 8, то и все данно...
Число Число — одно из основных понятий математики, возникшее впервые в связи с потребностями счета предметов и совершенствовавшееся затем по мере развития ...
Тетради «KUMON.Математика» Ни для кого не секрет, что материалы, которые обычно используют для обучения детей в школе, скучны. Конечно здесь многое зависит от учителя. Хороший п...
Три пишем, два в уме Многим из вас когда-нибудь приходилось и, скорее всего, еще не раз придется заниматься различными вычислениями. Вы, наверняка, заметили, что считат...

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

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