3.16. Евклидов алгоритм
Этот алгоритм назван в честь Евклида, потому что самое раннее известное его появление — в книге VII Начал. Однако, по мнению многих историков [например, Хит (1921), с. 399] алгоритм и некоторые его следствия, вероятно, были известны ранее. По меньшей мере, Евклид заслуживает чести за мастерское представление основ теории чисел на базе этого алгоритма.
Евклидов алгоритм используется для нахождения наибольшего общего делителя (нод) двух положительных целых чисел 
Первый этап — построить пару 
где
и затем просто повторить эту операцию, вычитая меньшее число из большего. То есть, если пара, построенная на шаге 
тогда пара, построенная на шаге 
Алгоритм завершается на первом шаге, когда 
и это общее значение — 
Это потому, что вычитание разностей сохраняет любые общие делители, следовательно, когда 
мы имеем
Абсолютная простота алгоритма облегчает выведение некоторых важных следствий. Евклид, конечно, не пользовался нашими обозначениями, но, тем не менее, он получил результаты, близкие к следующим.
1. Если 
тогда есть целые числа 
так что та 
Уравнения
последовательно показывают, что 
целые 
линейные комбинации, та 
a и b; следовательно, 
тоже, следовательно, 
тоже и, наконец, это истинно об 
Но 
поскольку 
следовательно, 
для некоторых целых чисел 
2. Если 
простое число, которое делит 
тогда 
делит а или 
(свойство простого делителя).
Чтобы увидеть это, предположим, что 
не делит а. Тогда, поскольку 
не имеет других делителей, кроме 1, мы имеем 
Следовательно, по предыдущему результату мы получаем целые числа 
так что
Умножение каждой стороны на 
дает
По предположению, 
делит 
следовательно, 
делит оба члена в левой части, и поэтому 
делит 
правой части.
3. Каждое положительное целое число имеет однозначное разложение на простые числа (основная теорема арифметики).
Предположим, напротив, что некоторое целое число 
имеет два разных разложения на простые числа:
Выделяя общие множители, если это необходимо, мы можем допустить, что есть 
которое не находится среди 
Но это противоречит предыдущему результату, потому что 
делит 
однако оно не делит какое-либо из 
индивидуально, поскольку есть простые числа 
Упражнения
(см. скан)
