Решения

5.1. а) Так как 36 = 2²*3² и 20 = 2²*5, то (36, 20) = 2² = 4.

б) Так как 1365 = 3*5*7*13 и 1225 = 5²*7², то (1365, 1225) = 5*7 = 35.

в) Так как 1189 = 29*41 и 589 = 19*31, то (1189, 589) = 1.

5.2. Докажем, что все общие делители пары чисел а и b являются общими делителями пары чисел b и r и, наоборот, все общие делители пары чисел b и r являются общими делителями пары чисел а и b. Тогда и наибольшие общие делители обеих пар будут совпадать.

Пусть d - какой-нибудь общий делитель чисел а и b. Так как a = qb + r, то число r = a - qb также делится на d (ибо оно есть разность чисел а и qb, кратных d). Поэтому число d является общим делителем чисел b и г. Аналогично, если числа b и r имеют общий делитель d, то тот же делитель будет иметь и число a = qb + r, т. е. число d будет общим делителем чисел а и b.

В случае r = 0 получаем, что наибольший общий делитель пары чисел а и b равен наибольшему делителю числа b (не равного нулю), т. е. самому числу b.

5.3. Заметим, что остаток от деления любого числа на число а обязательно меньше самого числа а. Поэтому последовательность ненулевых остатков удовлетворяет неравенствам

a₂>a₃>a₄>a₅>...>0 и не может быть бесконечной, так как она содержит не более a₂ чисел. Следовательно, описанный алгоритм не может продолжаться бесконечно. Если же число a_n разделится на а_n+1 нацело, то, согласно результату задачи 5.2, будут выполнены равенства

(a₁, a₂) = (a₂, a₃) = (a₃, a₄) = ... = (a_n , a_n+1) = a_n+1, т. е. наибольший общий делитель пары чисел a₁ и a₂ будет равен a_n+1.

5.4. а) Так как

36 = 1*20 + 16, 20 = 1*16 + 4, 16 = 4*4,

то (36, 20) = 4.

б) Так как

1365 = 1*1225 + 140, 1225 = 8*140 + 105, 140 = 1*105 + 35, 105 = 3*35,

то (1365, 1225) = 35.

в) Так как

1189 = 2*589 + 11, 589 = 53*11 + 6, 11 = 1*6 + 5, 6 = 1*5 + 1, 5 = 1*5,

то (1189, 589) = 1.

5.5. Найдем наибольший общий делитель пары чисел, стоящих в числителе и знаменателе дроби, и сократим дробь на этот делитель.

а) Воспользуемся алгоритмом Евклида:

2147 = 1*1577 + 570, 437 = 3*133 + 38,

1577 = 2*570 + 437, 133 = 3*38+19,

570 = 1*437 + 133, 38 = 2*19,

откуда (2147, 1577) = 19. Произведя деление числителя и знаменателя дроби на 19, находим

б) Заметим вначале, что числитель и знаменатель исходной дроби делятся на 6, поэтому ее можно сократить на 6 и получить дробь ²²¹/₂₀₂₃. Теперь применим алгоритм Евклида:

2023 = 9*221 + 34, 221 = 6*34 + 17, 34 = 2*17.

Таким образом, (2023, 221) = 17 и дробь можно сократить еще на 17:

5.6. Из прямоугольника размером 135*40 сначала вырезаны квадраты со стороной, равной меньшей стороне этого прямоугольника, т.е. 40. Количество таких квадратов равно частному от деления 135 на 40 с остатком:

135 = 3*40 + 15. Из оставшегося прямоугольника размером 40*15 вырезаны квадраты со стороной 15, которых, согласно делению 40 на 15 с остатком

40= 2*15 + 10, можно вырезать два. Из оставшегося прямоугольника размером 15*10 вырезан один квадрат со стороной 10, что соответствует делению 15 на 10 с остатком:

15 = 1*10 + 5. Наконец, последний прямоугольник размером 10*5 разрезан на два квадрата со стороной 5, так как

10 = 2*5. Как показывает приведенный анализ, рассмотренный способ разрезания на квадраты прямоугольника размером а₁*а₂, по существу, является демонстрацией алгоритма Евклида нахождения наибольшего общего делителя пары чисел а₁ = 135 и а₂ = 40. Вообще прямоугольник размером а₁*а₂ можно разрезать на квадраты со сторонами а₂, а₃, а₄, ..., а_n+1 в полном согласии с формулами алгоритма Евклида (см. задачу 5.3), причем последовательные частные q₁, q₂, ..., q_n укажут количества соответствующих квадратов.

5.7. Цепочку равенств, получающихся при нахождении наибольшего общего делителя пары чисел а₁ и а₂ с помощью алгоритма Евклида (см. задачу 5.3), перепишем следующим образом:

Подставляя в первую строчку вместо дроби ^а₂/_а3 ее выражение из второй строчки, находим

Подставляя сюда вместо дроби ^а₃/_а4 ее выражение из третьей строчки, имеем

Производя аналогичные подстановки и далее, из предпоследней строчки получим равенство

в котором останется лишь подставить вместо дроби ее значение q_n из последней строчки, после чего выражение будет удовлетворять всем требованиям задачи: все числа q₂, q₃, ..., q_n являются натуральными, так как а₂>а₃>...>a_n-1>a_n>a_n+1, а число q₁ является целым (если a₁≥a₂, то натуральным, а если а₁<а₂, то нулевым).

5.8.

5.9. Последовательные операции по свертыванию цепной дроби сводятся к операциям двух типов: сложение и деление . Докажем, что если ^a/_b несократимая дробь, то в результате операции любого из указанных двух типов получается также несократимая дробь. Действительно, операция первого типа приводит к дроби , числитель и знаменатель которой не имеют общих делителей, поскольку (см. решение задачи 5.2) справедливы равенства (qb + a, b) = (b, a) = 1. Операция второго типа приводит к дроби ^b/_a которая также несократима, ибо (a, b) = (b, а) = 1. Таким образом, раз дробь ¹/_qn несократима, то на каждом шагу, в том числе и на последнем, при свертывании цепной дроби мы получаем несократимую дробь.

Например, для заданной в задаче сократимой дроби имеем

5.10. Для дроби

имеем следующие подходящие дроби:

5.11. Решение этой задачи может показаться на первый взгляд совсем очевидным, поскольку для любой дроби ^a/_b можно сначала соединить параллельно b единичных сопротивлений, получив сопротивление, равное ¹/_b, а затем размножить эту схему в а экземплярах, соединив их последовательно. При этом в конечном счете нам понадобится а*b единичных сопротивлений. Например, для такого решения п. а) их нужно 7*2 = 14 штук, а для решения п. б) -10*7 = 70 штук. Как показывает приводимое ниже решение, этот очевидный способ далеко не самый экономный: в п. а) достаточно иметь всего 5, а в п. б) - 6 сопротивлений.

Рис. 6

а) Соединив параллельно два единичных сопротивления, получим сопротивление ¹/₂. Присоединив к нему последовательно еще три единичных сопротивления, мы получим сопротивление (рис. 6).

б) С учетом разложения требуемое сопротивление можно получить следующим образом: соединим последовательно одно единичное сопротивление и блок, в котором параллельно соединены три сопротивления - два единичных и блок из трех последовательных единичных сопротивлений (рис. 7). Тогда сопротивление второго блока будет равно 3, а первого - будет равно Общее же сопротивление как раз и будет составлять ¹⁰/₇.

Рис. 7

в) Пусть дробь ^a/_b разложена в цепную дробь (см. задачу 5.7)

Тогда соединим последовательно q₁ единичных сопротивлений и первый блок, в котором соединим параллельно q₂ единичных сопротивлений и второй блок, в котором соединим последовательно q₃ единичных сопротивлений и третий блок и т. д. Так, чередуя последовательное и параллельное соединения при составлении каждого последующего блока, мы на предпоследнем шаге соединим последовательно или параллельно q_n-1 единичных сопротивлений и (n-1)-й блок, в котором соединим, наоборот, параллельно или последовательно q_n единичных сопротивлений. Всего нам понадобится q₁ + q₂ + ... + q_n сопротивлений, что, как правило, меньше, чем a*b.

Докажем, что полученная схема имеет сопротивление ^a/_b. Если мы временно отсоединим от цепи весь первый блок, то сопротивление будет равно q₁, т. е. первой подходящей дроби к данной цепной дроби. Если временно отсоединим от цепи не первый, а второй блок, то сопротивление неполного первого блока будет равно ¹/_q2 и общее сопротивление будет равно т. е. второй подходящей дроби. Если отсоединим от цепи не второй, а третий блок, то сопротивление неполного второго блока будет равно q₃, первого -

и общее сопротивление будет равно третьей подходящей дроби. Продолжая эти рассуждения до конца, мы придем к тому, что если отсоединить только (n-1)-й блок, то общее сопротивление будет равно (n-1)-й подходящей дроби. Наконец, если ничего не отсоединять, то общее сопротивление будет равно последней подходящей дроби, т. е. самой цепной дроби, равной ^a/_b.

5.12. а) Так как - несократимая дробь, то P₁ = q₁, Q₁ = 1. Так как - несократимая дробь, то P₂ = q₁q₂ + 1, Q₂ = q₂. Для k = 3 получаем

откуда имеем Р₃ = Р₂q₃ + Р₁, Q₃ = Q₂q₃ + Q₁, т. е. при k = 3 формулы справедливы, Пусть они уже доказаны для значения k-1:

Тогда, заменяя q_k-1 выражением мы из дроби получим k-ю подходящую дробь

откуда имеем P_k = Р_k-1q_k + Р_k-2, Q_k = Q_k-1q_k + Q_k-2, т.е. формулы справедливы и для значения k (несократимость каждой из дробей была доказана в решении задачи 5.9).

б) В силу формул п. а) при k = 2, ..., n имеем

Поэтому для любого значения k = 2, ..., n получаем

что и требовалось доказать,

5.13. Если бы мы захотели приблизить данную дробь десятичной дробью то для достижения заданной точности потребовалось бы подобрать значения a и k из неравенства Проверка дробей показывает их непригодность и убеждает нас в том, что такой перебор значений весьма затруднителен, да и вряд ли приведет к успеху".

Попробуем приблизить данную дробь с помощью подходящих дробей к цепной дроби

Первая подходящая дробь ³/₁ дает погрешность а значит, не годится. Зато вторая подходящая дробь, равная ²²/₇, отличается от третьей, равной исходной дроби, на величину

(см. соотношение п. б) задачи 5.12 при k = 3). Таким образом, шестеренки с 22 и 7 зубьями удовлетворяют всем условиям задачи.