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 нацело. Запись этого алгоритма можно оформить так:
(числа q1, q2, ..., qn будем называть в дальнейшем последовательными частными).
Докажите, что описанный алгоритм обязательно закончится (т. е. при некотором значении 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. Цепная дробь Одним из применений алгоритма Евклида является представление дроби a1/a2 в виде
где q1 - целое число, a q2, q3, ..., qn - натуральные числа. Такое выражение называется цепной (конечной непрерывной) дробью. Докажите, что любую дробь a1/a2 можно разложить в цепную дробь, в которой числа q1, ..., qn являются последовательными частными алгоритма Евклида для нахождения наибольшего общего делителя пары чисел a1 и a2.
5.8. Разложение в цепную дробь Разложите следующую дробь в цепную дробь:
а) 7/3; б) 84/39; в) 33/78.
5.9. Свертывание цепной дроби Если в цепной дроби (см. задачу 5.7), начиная с конца, последовательно произвести указанные в ней операции по правилам действий с дробями, то в итоге получится обыкновенная дробь, разумеется, равная исходной.
Докажите, что полученная таким образом дробь будет несократимой. На основании этого утверждения сократите дробь 155/93, разложив ее в цепную дробь, а затем свернув в обыкновенную.
5.10. Подходящие дроби Пусть задана цепная дробь с последовательными частными q1, q2, ..., qn (см. задачу 5.7). Выражения
называются подходящими дробями порядка 1, 2, 3, ..., n соответственно. Разложите дробь 13/29 в цепную дробь и выпишите все подходящие к ней дроби. Обратите каждую из подходящих дробей в обыкновенную.
5.11. Комбинирование сопротивлений
Рис. 4
Из курса физики вам, наверняка, известно, что если соединить несколько сопротивлений R1, R2, ..., Rk в электрической цепи последовательно (рис. 4), то общее сопротивление будет равно R1 + R2 + ..., + Rk, а если соединить эти же сопротивления параллельно (рис. 5), то общее сопротивление окажется равным
Рис. 5
А теперь представьте, что у вас есть большое количество одинаковых единичных сопротивлений. Можно ли, комбинируя их в электрической цепи специальным образом, составить схему, имеющую сопротивление:
а) 7/2; б) 10/7; в) вообще a/b?
5.12. Кое-что о подходящих дробях Пусть для заданной цепной дроби с последовательными частными q1, q2, ..., qn несократимые дроби
являются результатами свертывания подходящих дробей порядка 1, 2, ..., n соответственно (см. задачу 5.10). Докажите справедливость соотношений: