4.2 ПРОСТЫЕ ЧИСЛА

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

Некоторые числа кажутся, но не являются простыми, подобно числам Эти и другие числа, которые имеют три и более делителей, называются составными. Каждое большее 1 целое число — либо простое, либо составное, но не то и другое одновременно.

Простые числа крайне важны, ибо это те „кирпичики", из которых строятся все целые положительные числа — всякое целое положительное число может быть записано в виде произведения простых чисел:

Так, (Произведе-ния, обозначаемые знаком аналогичны суммам, обозначаемым знаком , в том смысле, как это разъяснялось в упр. 2.25. Если то такое произведение считается пустым, а его величина равна 1 по определению — именно так число оказывается представленным с помощью Подобное разложение на множители всегда возможно, ибо если число не является простым, то оно имеет делитель такой, что следовательно, можно записать в виде а (по индукции) могут быть записаны в виде произведений простых чисел.

Более того, разложение (4.10) единственно: возможен только один способ записи числа в виде произведения простых чисел в неубывающем порядке. Это утверждение называется основной теоремой арифметики и кажется настолько очевидным, что впору усомниться в необходимости его доказательства. Разве могут два разных набора простых чисел иметь одно и то же произведение? Конечно же, не могут, но не просто определению простых чисел" Так, если рассмотреть множество всех вещественных чисел вида где — целые, то произведение любых двух таких чисел снова будет числом того же вида, и можно было бы назвать такое число „простым" если оно не может быть разложено на множители нетривиальным способом. Число 6 имеет два представления, и тем не менее в упр. 36 показано, что в этой системе — все „простые" числа.

Следовательно, то, что разложение (4.10) единственно, надо доказать строго. Несомненно, если то имеется только одна

возможность, поскольку произведение (4.10) в этом случае должно быть пустым. Поэтому предположим, что и что все меньшие числа разлагаются на множители единственным образом. Допустим, что имеются два разложения

где все числа простые. Покажем, что Если это не так, то можно считать, что тем самым число меньше всех чисел Так как простые числа, их должен быть равен 1; следовательно, самоподтверждающий алгоритм Евклида дает целые числа а и такие, что Тогда

Итак, делит оба члена в левой части, поскольку следовательно, делит и правую часть Тогда число целое, — разложение на множители, в котором присутствует Однако так что оно допускает единственное разложение на множители (по индукции). Это противоречие показывает, что в конце концов должно быть равно Поэтому можно разделить оба разложения на получая Подобно этому и другие сомножители должны быть равны (по индукции) — тем самым наше доказательство единственности разложения завершено.

Иногда удобнее сформулировать основную теорему другим образом: любое целое положительное число может быть записано единственным образом в виде

Правая часть представляет собой произведение по бесконечно многим простым числам, однако для любого отдельного все показатели степени — за исключением нескольких — равны 0, так что соответствующие им сомножители равны 1. Следовательно, на самом деле — это конечное произведение, точно так же, как в действительности конечны многие „бесконечные" суммы, ибо большая часть их слагаемых равна нулю.

Формула (4.11) однозначно представляет так что последовательность можно рассматривать как (каноническую) систему представления целых положительных чисел. Например, представление в виде показателей простых числа 12 имеет вид а представление в виде показателей простых числа При умножении двух чисел их представления просто складываются. Другими словами,

Это означает, что

откуда непосредственно следует, что

Например, поскольку можно получить их НОД и HOK, взяв соответствующих показателей:

Если некоторое простое число делит произведение то оно делит либо число либо число а возможно, и оба из них — в силу теоремы о единственности разложения на множители. Однако составные числа этим свойством не обладают. К примеру, не простое число 4 делит но не делит ни 6, ни 10. Причина очевидна: в разложении (2-5) два простых сомножителя числа расщеплены на две части — следовательно, 4 не делит ни одну из частей. Но простое число нерасщепляемо, так что оно должно делить один из исходных сомножителей.