Страница 25 из 30
ГЛАВА 7
Арифметика в «Началах»
В «Началах» говорится преимущественно о геометрии.
Однако это сочинение также содержит три книги, написанные под явным влиянием пифагорейской школы и не зависящие от остальных. В них Евклид рассказывает об элементарных результатах теории делимости, в том числе о знаменитом алгоритме нахождения наибольшего общего делителя.
Для того чтобы понять книги VII, VIII и IX, необходимо владеть некоторыми основными понятиями. В книге VII Евклид дает все арифметические определения, которыми пользуется позже, но не представляет ни одного постулата. Самыми важными определениями являются следующие.
1 .Единица есть то, через что каждое из существующих считается единым.
2. Число — множество, составленное из единиц.
3. Часть есть число в числе, меньшее в большем, если оно измеряет большее.
4. «Части же — если оно его не измеряет».
5. Кратное же — большее от меньшего, если оно измеряется меньшим.
6. Четное число есть делящееся пополам.
7. Нечетное число есть [...] отличающееся на единицу от четного числа.
8. Четно-четное число есть четным числом измеряемое четное число раз.
9. Четно же нечетное есть четным числом измеряемое нечетное число раз.
10. Нечетно-четное есть нечетным числом измеряемое четным числом раз.
12. Простое число есть измеряемое только единицей.
13. Простые между собой числа суть измеряемые только единицей как общей мерой.
14. Составное число есть измеряемое некоторым числом.
21. Числа будут пропорциональны, когда первое от второго, а третье от четвертого будут или равнократными, или той же частью, или теми же частями.
23. Совершенное число есть то, которое будет равным своим частям (делителей).
Первое определение является чисто философским. В нем отрицается числовая природа единицы, хотя Евклид использо вал ее как число — например, в следующем определении. Он также различает понятия «часть» (2 — часть 6, так как является его делителем) и «части» (5 — «части» 6 по противоположной причине). Здесь наблюдается аналогия с книгой V, хотя в ней вместо «части» говорится об «отношении», гораздо более сложном понятии. «Части» — основа многих арифметических доказательств Евклида: он рассматривает их в книге VII и прибегает к ним в книгах VIII и IX. Евклид также устанавливает различие между четным числом (N = n + n = 2n) и нечетным (N = 2n + 1) и предлагает классификацию чисел (не очень точную) на основе формул, которые мы сегодня бы записали так:
2m, 2m(2n + + 1), (2m +1) (2n + 1). Самые важные понятия книги VII — понятие «первого» (простого) числа, «составного» и чисел, «первых между собой». Определение 20 сегодня выглядело бы так:
m/n = p/q
только если существует такое λ Є Q, при котором если n = λ х m, то q = λ х р.
В заключение Евклид приводит довольно спорное определение совершенного числа, которое вряд ли принадлежит пифагорейской школе VI века. Некоторые приписывают его Гиппократу Хиосскому.
Математика — царица наук, а арифметика — царица математики.
Карл Фридрих Гаусс
АЛГОРИТМ ЕВКЛИДА
Книга 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 = q0 ∙ n + r1 r1 < n
n = q1 ∙ r1 + r2 r2 < r1
r1 = q2 ∙r2 + r3 r3 < r2
...
rk-1 = qk ∙ rk.
С одной стороны, rk-2 = qk-1 ∙ rk-1 + rk, с другой — rk-1 = qk ∙ rk. Таким образом, rk-2 = qk-1 ∙ (qk ∙ rk) + rk = (qk-1 ∙ qk + 1) ∙ rk, где qk-1 ∙ qk + 1 — натуральное число. Следовательно, rk является точным делителем rk-2.
При помощи аналогичного рассуждения, но обращенного вперед, мы получаем, что если d является общим делителем m и n, так как по построению m = q0 ∙ n + r1, то r1 = m - q0 ∙ n, где m = m1 ∙ d, n=n1 ∙ d. Следовательно, r1 = m1 ∙ d - (q0 ∙ n1) ∙ d = (m1-(q0 ∙ n1)) ∙ d. Значит, d является делителем r1, что и требовалось доказать.
В книге X Евклид использует этот алгоритм для величин вообще, а не только для чисел, и приходит к выводу, что взаимное вычитание имеет конец, только если обе величины соизмеримы и, следовательно, могут быть выражены с помощью чисел. Другими словами, если они несоизмеримы, то взаимное вычитание можно производить бесконечно. Об этом говорится в предложениях 2 и 3 книги X. Несмотря на сделанные открытия, Евклиду не удалось полностью использовать потенциал этого метода так, как это сделали индийские и китайские математики.
АЛГОРИТМ ЕВКЛИДА В ДЕЙСТВИИ
Книга VII, предложение 17. Если число, умножая два числа, производит нечто, то возникающие из них будут иметь то же самое отношение, что и умножаемые [коммутативное свойство результата].
Книга VII, предложение 18. Если два числа, умножая некоторое число, производят нечто, то возникающие из них: будут иметь то же самое отношение, что и умножающие.
Книга VII, предложение 19. m/n = p/q, только если m х q = n х p.
Книга VII, предложение 20. Числа, наименьшие из имеющих то же самое отношение с ними, равное число раз измеряют имеющие то же самое отношение числа, причем большее измеряет большее, а меньшее — меньшее.
Книга VII, предложение 24. Если (p,m) = 1 , то (p,m х n) = 1.
Книга VII, предложение 29. Если p — первое число, не являющееся частью n, то (p,n) = 1.