Евклид. Геометрия

ГЛАВА 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) и предлагает классификацию чисел (не очень точную) на основе формул, которые мы сегодня бы записали так:

2^m, 2^m(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 = q₀ ∙ n + r₁ r₁ < n

n = q₁ ∙ r₁ + r₂ r₂ < r₁

r₁ = q₂ ∙r₂ + r₃ r₃ < r₂

...

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₀ ∙ n + r₁, то r₁ = m - q_{0 ∙} n, где m = m₁ ∙ d, n=n₁ ∙ d. Следовательно, r₁ = m₁ ∙ d - (q₀ ∙ n₁) ∙ d = (m₁-(q_{0 ∙} n₁)) ∙ d. Значит, d является делителем r₁, что и требовалось доказать.

В книге 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.

Книга VII, предложение 30. Если р — первое число и делитель m х n, то p — часть одного из множителей m и n.

Книга VII, предложение 31. Всякое составное число измеряется каким-то простым числом.

Книга VII, предложение 32. Всякое число или простое, или измеряется каким-то простым числом.

Книга IX, предложение 14. Если число будет наименьшим измеряемым данными простыми числами, то оно не измерится никаким иным простым числом, кроме первоначально измерявших его.

Книга IX, предложение 20. Простых чисел существует больше всякого предложенного количества простых чисел.

В доказательстве 31 книги X Евклид пользуется подразумевающимся постулатом. Он рассуждает следующим образом: пусть N— составное число, тогда его делителем (его частью) будет N’< N. Предположим, что это не простое число. Значит, оно, в свою очередь, составное и имеет делитель (часть) N" < Ν' < N и так далее. Невозможно, что не найдется никакого простого числа Р, потому что в противном случае у нас будет бесконечная последовательность... <Νⁿ< ... < Ν"< Ν'< Ν. Согласно Евклиду, это невозможно. Таким образом, он постулирует невозможность убывающей последовательности первых чисел.

Бог создал целые числа, все остальное — дело рук человека.

Леопольд Кронекер (1823-1891)

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

Предложение 14 книги IX иногда называют основной теоремой арифметики (каждое целое число больше 1 или простое, или может быть записано в виде произведения простых чисел), выраженной математическим языком той эпохи. Чтобы утверждать это с полным правом, нам нужно знать, отличаются эти простые числа или могут быть равны. Во втором случае мы получим основную теорему.

В предыдущих главах мы говорили об ограничениях, наложенных Аристотелем на использование понятия бесконечности. В предложении 20 книги IX {«Простых чисел существует больше всякого предложенного количества простых чисел») Евклид соблюдает это ограничение и проявляет большую осторожность, чтобы не сказать о «бесконечном ряде простых чисел». И тем не менее существует ли алгоритм, позволяющий получать все больше и больше простых чисел? Евклид ничего не говорил по этому поводу. Лишь позже, в «Арифметике» Никомаха Герасского (ок. 60 — ок. 120) рассказывается о решете Эратосфена — методе, названном по имени изобретшего его математика:

«Способ получения всех этих чисел Эратосфен назвал решетом, потому что здесь сначала берутся нечетные числа, все вместе и без различий между ними, а затем этим производящим методом отделяются, как посредством решета, первичные числа от составных. Способ решета состоит в следующем. Начинают с тройки, а потом располагают в ряд все числа, кратные трем, пропуская два числа через каждые три и убирая третье. Потом переходят к первому оставшемуся числу, пятерке; пропускают четыре числа и убирают пятое; затем то же проделывают с семеркой, и так дальше, начиная всякий раз с первого неубранного числа».

Хотя Евклид и дал правильное определение простых чисел, а также теорему, чтобы породить совершенные числа, он не снабдил ее никаким примером. Соответствующее предложение может показаться неясным, возможно потому что оно представлено в описательной форме.

Книга IX, предложение 36. Если от единицы откладывается сколько угодно последовательно пропорциональных чисел в двойном отношении до тех пор, пока вся их сумма не станет первым числом, [...] то возникающее число будет совершенным.

Евклид имеет в виду следующее:

Если 1,2, 2², 2³, ..., 2ⁿ последовательно удваивать, то их сумма будет

S_n=1 + 2 + 2² + 2³+...+ 2ⁿ = 2ⁿ⁺¹ -1; если S_n — простое число, то Р_n = 2ⁿ x S_n = 2ⁿx(2ⁿ⁺¹-1) — совершенное число (четное).

Евклиду удалось получить этот результат, потому что в предложении 35 книги IX он уже дал формулу, необходимую для сложения чисел из последовательности 1, 2, 2², 2³, ..., 2ⁿ. Он также обратил внимание, что единственные рассмотренные делители Р, 1, 2, 2², 2³,..., 2ⁿ и S_n, 2 х S_n, 2² х S_n, 2³ x S_n,..., 2^n-1 x S_n. Он сложил их и получил результат теоремы: сумму делителей 1, 2, 2², 2³, ..., 2ⁿ,

равную S_n = 2^{n + 1} - 1, и сумму делителей S_n, 2 x S ,2² x S ,2³ x S ,..., 2^n-1 x S и (2ⁿ - 1) x S . Сумма двух результатов — Р_n = S_n + (2n- 1) х S_n = 2ⁿ х S_n = 2ⁿ х (2^{n + 1} - 1). Ч. Т. Д.

В «Арифметике» Никомах Герасский устанавливает, что совершенными числами являются 6,28,496 и 8126. Из этого он делает следующие выводы.

1. Совершенные числа (четные) оканчиваются на 6 и 8 (верно).

2.Они чередуются (неверно).

3.Существует одно совершенное число на каждый десятичный порядок — среди единиц, десятков, сотен, тысяч и так далее (неверно).

В XVIII веке Эйлер доказал теорему, взаимодополняющую теорему Евклида: каждое совершенное число (четное) имеет вид 2ⁿ х (2ⁿ⁺¹-1), где 2ⁿ⁺¹-1 — простое число. На сегодняшний день все еще существуют нерешенные вопросы относительно совершенных чисел: неизвестно, бесконечен ли их ряд и существуют ли совершенные нечетные числа.

Начнем с последовательности нечетных чисел.

Начиная с 3 уберем третьи числа через каждые два.

Начиная с 5 уберем пятые числа через каждые пять и получим следующее.

И так далее. Вот список простых чисел до тысячи.

Последняя задача, которую стоит разобрать, — это алгоритм получения пифагоровых троек — трех натуральных чисел, подтверждающих теорему Пифагора, например 3, 4, 5; 5, 12, 13 и так далее, то есть таких чисел a, b и с, при которых а² + b² = с².

Возможно, в Древнем Вавилоне знали метод нахождения пифагоровых троек, о чем свидетельствует вавилонская глиняная табличка, которую называют Plimpton 322. В ней содержится несколько троек, выраженных в шестидесятых долях. Пифагору приписывается авторство метода, позволяющего получить эти числа, основанного на гномоне квадратных чисел. Квадратное число — это то, которое можно выразить в виде квадрата (см. рисунок). Следовательно, мы имеем n^² + (2n + 1) = (n+1)^². Для того чтобы составить пифагорову тройку, в которой катет и гипотенуза — два последовательных числа, гномон тоже должен быть квадратом, то есть 2n + 1 = k^², где k — нечетное число. Следовательно,

n = (k² - 1)/2, k нечетное.

Так можно получить тройки n = (k² - 1)/2, k, n +1 = (k² + 1)/2,

где k — нечетное число, образующее следующие таблицы.

Последовательность квадратных чисел 1, 4, 9,16 (n - 1)^², n^². Чтобы перейти от c_n = n^² к c_{n + 1} = (n + 1)^², нужно добавить гномон, равный 2n +1. То есть между ними всегда будет нечетное число.

Таким образом можно получить бесконечное множество троек, но не все: например, здесь не хватает тройки 8, 15, 17, в которой разница между катетом и гипотенузой равна двум единицам.

Платону приписывают обобщение этого метода Пифагора. Необходимо перейти от (n - 1)^² к (n + 1)^². Для этого надо сложить два гномона: 2n - 1, позволяющий перейти от (n - 1)^² к n^², и 2n + 1, позволяющий перейти от n^² к (n + 1)^². Всего надо добавить 4n. То есть (n - 1)^² + 4n = (n + 1)^². Значит, n должно быть квадратным числом: n = k^². Так мы получаем тройки k^² - 1, 2k и k^² + 1. При k = 4 мы получим уже упомянутую тройку 8,15,17. Запишем это в виде таблицы.

Приведенные таблицы различаются: в первой представлены простые тройки, то есть такие, у которых нет общего делителя; во второй цифры в столбцах с нечетным к можно разделить на 2, и мы получим некоторые значения первой таблицы. Можно сказать, что первая таблица включена во вторую. Но существует ли алгоритм, позволяющий получить все возможные пифагоровы тройки? Ответ на этот вопрос положительный, и дает его сам Евклид в лемме 1 книги X:

Существуют два квадратных числа, которые вместе образуют еще один квадрат.

Не вдаваясь в подробности, скажем, что Евклид использовал алгоритм α = λ^²-μ^², b = 2λμ, c = λ^² + μ^², где λ и μ — взаимно простые числа, имеющие разную четность. Это условие необходимо соблюдать для того, чтобы тройки не повторялись и все составляющие их числа были простыми, без общих делителей. Действительно, нас интересуют только простые тройки, так как очевидно, что при любом натуральном числе k 3k, 4k, 5k тоже будут натуральными, ведь 3, 4 и 5 — натуральные. Все вышесказанное справедливо для любой пифагоровой тройки a, b, c.