Josep Carrera: Трехмерный мир. Евклид. Геометрия

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. Несмотря на сделанные открытия, Евклиду не удалось полностью использовать потенциал этого метода так, как это сделали индийские и китайские математики.

Книга 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 и так далее. Невозможно, что не найдется никакого простого числа Р, потому что в противном случае у нас будет бесконечная последовательность... <���Ν n< ... < Ν"< Ν'< Ν. Согласно Евклиду, это невозможно. Таким образом, он постулирует невозможность убывающей последовательности первых чисел.

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

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

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

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

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