ГЛАВА III

АЛГОРИФМ ЕВКЛИДА И ЦЕПНЫЕ ДРОБИ

S 8. Алгорифм Евклида

Элементарная арифметика учит двум существенно различным

способам нахождения наибольшего общего делителя двух чисел.

Первый способ состоит в разложении данных чисел на простые

множители с последующим составлениерг из этих множителей по

известным правилам наибольшего общего делителя данных чисел.

Второй способ есть так называемый способ последовательного деле-

пия: первое из данных чисел делится на второе, второе — на оста-

ток первого делеиия, первый остаток на второй и т. п. Так как

при этом каждый остаток меньше предыдущего и все они неотри-

цательны, то после конечного числа делений мы должны получить

остаток, равный нулю. Последний положительный остаток в этом

процессе й будет наибольшим общим делителем двух данных чисел.

Этот процесс, иазываемый обычно «алгорифмом Евклида», замеча-

телен своей элементарностью: для его применения нет надобности

знать, как составлены данные числа мз простых множителей,

и в этом его существенное преимущество перед первым способом.

Однако, несмотря на свою простоту и элементарность, алгорифм

Евклида и по существу и исторически имеет глубокое методологи-

ческое значение. Он может быть положен в основание всей теории

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

неизвестными (см. стр. 284); на нём строятся, как известно, отыскание

общей меры двух величин, а вместе с тем и вся теория измерения;

наконец, он служит естественным исходным пунктом теории цепных

дробей —самого сильного из всех методов арифметики иррациональных

чисел, имеющего также и непосредс гвенное практическое значение.

Мы поэтому со всею тщательностью рассмотрим теперь этот

алгорифм и его арифмегические приложения.

Пусть даны два целых числа а и Ь, из которых второе положи-

тельно. Будем делить а на Ь и обозначим соответственно через ая

и частное и остаток этого деления, так что

(1)