Примени математику (Гашков, Сергеев) - страница 30
Алгоритм Евклида применяется ко многим с виду разнородным объектам. Нахождение наибольшего общего делителя, разложение дроби в цепную дробь, приближение дроби более простыми, решение уравнений в целых числах - вот далеко не полный перечень приложений этого алгоритма, с которыми вы познакомитесь в настоящем и следующем параграфах.
5.1. Разлагая на множители Найдите наибольший общий делитель пары чисел a и b путем разложения их на простые множители:
а) а = 36, b = 20; б) а = 1365, b = 1225; в) а = 1189, b = 589.
5.2. Первый шаг Докажите, что если число а при делении на b дает остаток r, то
(a, b) = (b, r), т. е. наибольший общий делитель пары чисел а и b совпадает с наибольшим общим делителем пары чисел b и r. Каким будет наибольший общий делитель пары чисел а и b, если число а делится на b нацело?
5.3. Алгоритм Евклида Для нахождения наибольшего общего делителя пары натуральных чисел а>1 и а>2 поступают следующим образом: деля а>1 на а>2, получают остаток а>3, затем, деля а>2 на а>3, получают остаток а>4, затем, деля а>3 на а>4, получают остаток а>5 и так далее до тех пор, пока некоторое число а>n не разделится на а>n+1 нацело. Запись этого алгоритма можно оформить так:
(числа q>1, q>2, ..., q>n будем называть в дальнейшем последовательными частными).
Докажите, что описанный алгоритм обязательно закончится (т. е. при некотором значении n число а>n разделится на а>n+1 нацело), а число а>n+1 окажется равным наибольшему общему делителю пары чисел а>1 и а>2.
5.4. Не разлагая на множители Применяя алгоритм Евклида, найти наибольший общий делитель пары чисел а и b, указанных в п. а), б), в) задачи 5.1.
5.5. Найдя наибольший общий делитель Сократите дробь:
5.6. Разрезание на квадраты На рис. 3 изображен прямоугольник размером 135*40, который разрезан на квадраты различной величины. Установите размеры квадратов и укажите связь между разрезанием на квадраты любого прямоугольника с целочисленными сторонами и алгоритмом Евклида (см. задачу 5.3).
Рис. 3
5.7. Цепная дробь Одним из применений алгоритма Евклида является представление дроби >a>1/>a>2 в виде
где q>1 - целое число, a q>2, q>3, ..., q>n - натуральные числа. Такое выражение называется цепной (конечной непрерывной) дробью. Докажите, что любую дробь >a>1/>a>2 можно разложить в цепную дробь, в которой числа q>1, ..., q>n являются последовательными частными алгоритма Евклида для нахождения наибольшего общего делителя пары чисел a>1 и a>2.
5.8. Разложение в цепную дробь Разложите следующую дробь в цепную дробь:
а) >7/>3; б) >84/>39; в) >33/>78.
5.9. Свертывание цепной дроби