§ 1. Простые числа

1. Основные факты

Многие утверждения в области теории чисел, как и математики вообще, относятся не к отдельным объектам, скажем к числу 5 или числу 32, а к целому классу объектов, имеющих какое-то общее свойство; примерами могут служить класс всех четных чисел

или класс чисел, делящихся на 3,

или класс квадратов целых чисел

и т. д.

В теории чисел особенно важную роль играет класс всех простых чисел. Очень многие числа могут быть разложены на меньшие множители: 10 = 2*5, 111 = 3*37, 144 = 3*3*2*2*2*2 и т. п. Числа, которые таким образом не разлагаются, носят название простых. Точнее, простым называется такое целое число р, большее единицы, которое не имеет иных множителей, кроме единицы и самого себя. (Число а есть множитель, или делитель, числа b или делит число b, если существует такое целое число с, что b = ас.) Числа 2, 3, 5, 7, 11, 13, 17, ... - простые, тогда как например число 12 не является простым, так как 12 = 3*4. Значение класса простых чисел заключается в том, что каждое число может быть представлено как произведение простых: если данное число не простое, то его можно последовательно разлагать на множители до тех пор, пока все множители не окажутся простыми; так, например, 360 = 3*120 = 3*30*4 = 3*3*10*2*2 = 3*3*5*2*2*2 = 2³*3²*5. Число, отличное от 0 и 1 и не являющееся простым, называется составным.

Один из первых вопросов, возникающих по поводу класса простых чисел, заключается в том, существует ли только конечное число различных простых чисел или же класс простых чисел содержит бесконечное число членов подобно классу всех целых чисел, частью которого он является. Ответ таков: простых чисел существует бесконечное множество.

Данное Евклидом доказательство существования бесконечного множества простых чисел представляет собой типичный образец математического рассуждения. В основе его лежит "косвенный метод" (доказательство от противного, приведение к абсурду). Сделаем попытку допустить, что рассматриваемое предложение неверно. Это означало бы, что существует лишь конечное число простых чисел, хотя, может быть, и очень много - скажем, около миллиарда; тогда допустим, что это число, представленное в "общей" или "неопределенной" форме, будет n. Пользуясь знаками, мы можем обозначить все простые числа через р₁, р_2,, ..., р_n. Всякое иное число тем самым - составное и должно делиться по меньшей мере на одно из простых чисел р₁, р₂, ..., р_n. А теперь мы придем к противоречию, именно, построим число А, которое будет отлично от каждого из чисел р₁, р₂, ..., р_n, так как будет больше их всех и тем не менее не будет делиться ни на одно из них. Вот это число:

Как видно, оно равно единице плюс произведение тех чисел, которые образуют совокупность всех простых чисел. Число А больше, чем любое из чисел р, и потому должно быть составным. Но при делении на р₁, на р₂ и т. д. Л дает всякий раз остаток 1, таким образом, А не делится ни на одно из чисел р. Сделанное нами допущение, что существует лишь конечное число простых чисел, приводит, таким образом, к противоречию,, так что приходится заключить, что это допущение ошибочно, а, следовательно, истинным может быть только противоположное ему. Итак, теорема доказана.

Хотя это доказательство и "косвенного" характера, все же небольшое его видоизменение приводит по крайней мере теоретически к методу построения бесконечной последовательности простых чисел. Предположим, что, исходя из некоторого простого числа, скажем р₁ = 2, мы уже нашли n простых чисел р₁, р₂, ...., р_n; заметим, далее, что число p₁p₂...p_n + 1 или простое, или содержит множителем простое число, отличное от тех, которые уже найдены. Так как такой множитель всегда может быть найден (хотя бы непосредственными пробами), то в обоих названных случаях мы в итоге получаем новое простое число р_n+1; продолжая таким же образом дальше, убеждаемся, что последовательность простых чисел, которые мы действительно можем построить, не имеет конца.

Упражнение. Выполнить намеченное построение, начиная с простых чисел р₁ = 2, р₂ = 3; найти еще пять простых чисел.

Если какое-нибудь число представлено в виде произведения простых множителей, то эти множители можно, конечно, располагать в каком угодно порядке. Занимаясь разложением чисел на простые множители, мы очень скоро приходим к заключению, что с точностью до порядка сомножителей разложение любого числа N на простые множители обладает свойством единственности: каждое натуральное число N, большее единицы, может быть разложено на простые множители только одним способом. Это утверждение кажется на первый взгляд таким очевидным, что неспециалист склонен обыкновенно отвергать необходимость его доказательства. Все же рассматриваемое предложение отнюдь не тривиально; с другой стороны, его доказательство, хотя и совсем элементарного содержания, требует более или менее тонких рассуждений. Классическое доказательство этой "основной теоремы арифметики", данное Евклидом, базируется на методе ("алгорифме") нахождения общего наибольшего делителя двух чисел. Этот метод будет нами рассмотрен на стр. 68. Здесь же мы вместо того приведем доказательство менее почтенной давности, которое несколько короче, чем доказательство Евклида, и вместе с тем выглядит несколько более "софистическим". Оно также является типичным образцом "косвенного" рассуждения. Мы допустим, что существует такое число, которое может быть разложено на простые множители двумя существенно различными способами, и это допущение приведет нас к противоречию. Возникновение противоречия будет свидетельствовать о том, что гипотеза о существовании числа, допускающего два существенно различных разложения на простые множители, несостоятельна; и отсюда мы заключим, что разложение чисел на простые множители обладает свойством единственности.

^* Если существует хоть одно число, допускающее два существенно различных разложения на простые множители, то существует непременно и наименьшее число, обладающее таким свойством (см. стр. 43),

где через р и q обозначены простые числа. Меняя, если потребуется, порядок этих множителей, мы можем допустить, что

Заметим, что р₁ отлично от q₁: иначе, деля равенство (1) на общий простой множитель, мы получили бы два существенно различных разложения на простые множители числа, которое было бы меньше, чем m, и это противоречило бы предложению о том, что m - наименьшее число, обладающее таким свойством. Следовательно, одно из двух: или р₁<q₁, или q₁<p₁. Пусть р₁<q₁. (Если бы оказалось q₁<p₁ ( то в дальнейшем рассуждении достаточно было бы поменять местами буквы р и q.) Рассмотрим целое число

Подставляя вместо m его два выражения, взятые из равенства (1), мы можем представить число m' в любом из двух видов:

Из равенства (4) следует, что m' - положительное число, так как р₁<q₁; из равенства (2) следует, с другой стороны, что m' меньше чем m. Но раз так, то разложение m' на множители должно быть единственным (с точностью до порядка сомножителей). Из равенства (3) далее видно, что р₁ входит множителем в m'; значит, из равенства (4) можно в таком случае заключить, что р₁ входит множителем или в q₁ - р₁ или в q₂q₃ ... q_s. (Это вытекает из единственности разложения m на простые множители; см. рассуждение в следующем абзаце.) Но последнее невозможно, так как все q больше чем р. Поэтому р₁ должно входить множителем в q₁ - р₁, т. е. q₁ - р₁ должно делиться на р₁. Другими словами, существует такое целое число h, что

Но это значит, что q₁ делится на р₁, чего, однако, быть не может, так как по предположению q₁ - число простое. Противоречие, к которому мы пришли, показывает несостоятельность первоначально сделанного допущения, чем и заканчивается доказательство основной теоремы арифметики.

Вот одно важное следствие основной теоремы. Если простое число р входит множителем в произведение ab, то оно непременно входит множителем или в а, или в b. В самом деле, если бы р не входило множителем ни в а, ни в b, то, перемножая разложения на простые множители чисел а и b, мы получили бы разложение на простые множители числа ab, не содержащее множителя p. С другой стороны, так как предполагается, что р входит множителем в произведение ab, то это значит, что существует такое целое число t, что

Поэтому, перемножая р и разложение на простые множители числа t, мы получим разложение на простые множители числа ab, содержащее множитель р. Таким образом, приходится признать, что существует два различных разложения числа ab на простые множители, а это противоречит основной теореме.

Примеры. Если установлено, что 2652 делится на 13 и что 2652 = 6*442, то отсюда можно сделать заключение, что 442 делится на 13. С другой стороны, 240 делится на 6 и притом 240 = 15*16, но ни 15, ни 16 не делятся на 6. Этот пример показывает, что условие основной теоремы относительно того, что число р простое, является существенным.

Упражнение. Чтобы найти все делители числа а, достаточно разложить а в произведение

где все множители р_i - простые и различные, причем каждый из них возводится в некоторую степень. Все делители числа а имеют вид

где показатели β - произвольные целые числа, подчиненные условиям

Докажите это утверждение. В качестве следствия установите, что число всех делителей а (включая 1 и само а) равно произведению

Так, например,

имеет 5*3 делителей. Вот они: 1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 9, 18, 36, 72, 144.