Карл Фридрих Гаусс
АЛГОРИТМ ЕВКЛИДА
Книга VII начинается со знаменитого алгоритма Евклида, который изучается еще в школе:
если даны два числа т и п, то существует число р, являющееся частью и m, и n.
Его смысл заключается в следующем: от большего числа, например m, вычитается меньшее, n, столько раз, сколько возможно. Остается число r < n и рассматривается пара n, r, процедура повторяется несколько раз, в результате чего мы имеем последовательность пар m, n; n, r, r, s; s, t; t, u; ...; х, y, y, z.
В какой-то момент 2 будет равна у, и это означает, что отнимать больше нечего. Выполняя обратное действие, мы убеждаемся, что у является делителем х и, в конце концов, что z делит и m, и n. К тому же это их наибольший общий делитель, так как любой общий для m и n делитель d делит также и 2.
Таким образом, z называется наибольшим общим делителем пары m и n. Сумма общих делителей m и n обычно обозначается как v. Если v равна единице, то m и n являются «первыми между собой». Этот метод определения отношений между числами называется взаимным вычитанием. Мы уже рассматривали его с геометрической точки зрения, когда анализировали несоизмеримость стороны и диагонали квадрата. Основное различие между этими случаями состоит в том, что, согласно Евклиду, в арифметике этот процесс должен рано или поздно подойти к концу, а в геометрии он продолжается до бесконечности.
АЛГОРИТМ ЕВКЛИДА В ДЕЙСТВИИ
Из алгоритма Евклида следует, что
m = q>0 ∙ n + r>1 r>1 < n
n = q>1 ∙ r>1 + r>2 r>2 < r>1
r>1 = q>2 ∙r>2 + r>3 r>3 < r>2
...
r>k-1 = q>k ∙ r>k.
С одной стороны, r>k-2 = q>k-1 ∙ r>k-1 + r>k, с другой — r>k-1 = q>k ∙ r>k. Таким образом, r>k-2 = q>k-1 ∙ (q>k ∙ r>k) + r>k = (q>k-1 ∙ q>k + 1)>> ∙ r>k, где q>k-1 ∙ q>k + 1 — натуральное число. Следовательно, r>k является точным делителем r>k-2.
При помощи аналогичного рассуждения, но обращенного вперед, мы получаем, что если d является общим делителем m и n, так как по построению m = q>0 ∙ n + r>1, то r>1 = m - q>0>∙ n, где m = m>1 ∙ d, n=n>1 ∙ d. Следовательно, r>1 = m>1 ∙ d - (q>0 ∙ n>1) ∙ d = (m>1-(q>0 ∙ n>1)) ∙ d. Значит, d является делителем r>1, что и требовалось доказать.
В книге X Евклид использует этот алгоритм для величин вообще, а не только для чисел, и приходит к выводу, что взаимное вычитание имеет конец, только если обе величины соизмеримы и, следовательно, могут быть выражены с помощью чисел. Другими словами, если они несоизмеримы, то взаимное вычитание можно производить бесконечно. Об этом говорится в предложениях 2 и 3 книги X. Несмотря на сделанные открытия, Евклиду не удалось полностью использовать потенциал этого метода так, как это сделали индийские и китайские математики.