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

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

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

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

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. Алгоритм Евклида Для нахождения наибольшего общего делителя пары натуральных чисел а₁ и а₂ поступают следующим образом: деля а₁ на а₂, получают остаток а₃, затем, деля а₂ на а₃, получают остаток а₄, затем, деля а₃ на а₄, получают остаток а₅ и так далее до тех пор, пока некоторое число а_n не разделится на а_n+1 нацело. Запись этого алгоритма можно оформить так:

(числа q₁, q₂, ..., q_n будем называть в дальнейшем последовательными частными).

Докажите, что описанный алгоритм обязательно закончится (т. е. при некотором значении n число а_n разделится на а_n+1 нацело), а число а_n+1 окажется равным наибольшему общему делителю пары чисел а₁ и а₂.

5.4. Не разлагая на множители Применяя алгоритм Евклида, найти наибольший общий делитель пары чисел а и b, указанных в п. а), б), в) задачи 5.1.

5.5. Найдя наибольший общий делитель Сократите дробь:

5.6. Разрезание на квадраты На рис. 3 изображен прямоугольник размером 135*40, который разрезан на квадраты различной величины. Установите размеры квадратов и укажите связь между разрезанием на квадраты любого прямоугольника с целочисленными сторонами и алгоритмом Евклида (см. задачу 5.3).

Рис. 3

5.7. Цепная дробь Одним из применений алгоритма Евклида является представление дроби ^a₁/_a2 в виде

где q₁ - целое число, a q₂, q₃, ..., q_n - натуральные числа. Такое выражение называется цепной (конечной непрерывной) дробью. Докажите, что любую дробь ^a₁/_a2 можно разложить в цепную дробь, в которой числа q₁, ..., q_n являются последовательными частными алгоритма Евклида для нахождения наибольшего общего делителя пары чисел a₁ и a₂.

5.8. Разложение в цепную дробь Разложите следующую дробь в цепную дробь:

а) ⁷/₃; б) ⁸⁴/₃₉; в) ³³/₇₈.

5.9. Свертывание цепной дроби Если в цепной дроби (см. задачу 5.7), начиная с конца, последовательно произвести указанные в ней операции по правилам действий с дробями, то в итоге получится обыкновенная дробь, разумеется, равная исходной.

Докажите, что полученная таким образом дробь будет несократимой. На основании этого утверждения сократите дробь ¹⁵⁵/₉₃, разложив ее в цепную дробь, а затем свернув в обыкновенную.

5.10. Подходящие дроби Пусть задана цепная дробь с последовательными частными q₁, q₂, ..., q_n (см. задачу 5.7). Выражения

называются подходящими дробями порядка 1, 2, 3, ..., n соответственно. Разложите дробь ¹³/₂₉ в цепную дробь и выпишите все подходящие к ней дроби. Обратите каждую из подходящих дробей в обыкновенную.

5.11. Комбинирование сопротивлений

Рис. 4

Из курса физики вам, наверняка, известно, что если соединить несколько сопротивлений R₁, R₂, ..., R_k в электрической цепи последовательно (рис. 4), то общее сопротивление будет равно R₁ + R₂ + ..., + R_k, а если соединить эти же сопротивления параллельно (рис. 5), то общее сопротивление окажется равным

Рис. 5

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

а) ⁷/₂; б) ¹⁰/₇; в) вообще ^a/_b?

5.12. Кое-что о подходящих дробях Пусть для заданной цепной дроби с последовательными частными q₁, q₂, ..., q_n несократимые дроби

являются результатами свертывания подходящих дробей порядка 1, 2, ..., n соответственно (см. задачу 5.10). Докажите справедливость соотношений:

5.13. Приближение цепной дроби Между двумя параллельными осями вращения требуется так установить зубчатую передачу, чтобы отношение угловых скоростей вращения было по возможности более близким к числу ³⁵⁵/₁₁₃. Один из способов состоит в том, чтобы получить точное значение указанного отношения, поместив на одной оси шестеренку с 355 зубьями, а на другой - со 113 зубьями. Нельзя ли подобрать две шестеренки имеющие меньше 25 зубьев каждая, обеспечив при этом абсолютную погрешность, не превышающую 0,002?