АЛГОРИТМ ЕВКЛИДА В ДЕЙСТВИИ
Книга 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 или простое, или может быть записано в виде произведения простых чисел), выраженной математическим языком той эпохи. Чтобы утверждать это с полным правом, нам нужно знать, отличаются эти простые числа или могут быть равны. Во втором случае мы получим основную теорему.