Глава VI. ЦЕПНЫЕ ДРОБИ

§ 1. Конечные цепные дроби

1. Алгоритм Евклида.

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

Другой метод решения этой задачи, свободный от указанного недостатка, изложен еще в книге Евклида «Начала» (III век до н. э.); его называют алгоритмом Евклида или способом последовательного деления. Изложим этот способ.

Напомним сначала некоторые свойства деления с остатком. Пусть а — целое число — натуральное число. Существуют такие целые числа (частное) и (остаток), что

Эти числа однозначно определены.

Справедливо следующее утверждение: если то наибольший общий делитель чисел а и совпадает с наибольшим общим делителем чисел и

В самом деле, обозначим наибольший общий делитель чисел через а наибольший общий делитель чисел и — через Из соотношения получаем, что является делителем и числа то есть будет общим (но не обязательно наибольшим) делителем чисел и Отсюда следует, что Обратно, из соотношения следует, что наибольший общий делитель чисел и является делителем числа , а значит, Из двух соотношений получаем

Теперь опишем алгоритм Евклида. Он заключается в том, что для целого числа а и натурального числа последовательно находят

две конечные последовательности чисел такие, что и

Тогда — наибольший общий делитель чисел а и Это следует из того, что по доказанному наибольшие общие делители пар чисел совпадают друг с другом. Но и потому наибольший общий делитель чисел и равен .

Заметим, что цепь равенств (1), выражающая алгоритм Евклида, не может быть бесконечной, так как из вытекает, что в (1) не более чем равенств.