Простые числа

Как мы только что убедились, любое положительное целое число может быть представлено в виде уникальной суммы различных степеней числа 2. В принципе, можно говорить, что числа, получаемые при возведении 2 в последовательные степени – это строительные блоки, из которых складываются положительные целые числа.

Примерно то же справедливо и отношении простых чисел и умножения: любое положительное целое число можно представить в виде произведения простых чисел (с той лишь разницей, что простые числа изучены куда меньше, чем степени основания 2, и знаем о них мы далеко еще не всё).

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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53…

Число 1 простым не является: у него всего один делитель (хотя, конечно, не только поэтому – есть и более веские причины, о которых мы поговорим чуть позже). Обратите также внимание: в этом ряду всего лишь одно четное – 2, что явно (а можно сказать и – выгодно) отличает ее от остальных простых чисел.

Положительное целое число, для которого имеются 3 и более делителя, называется составным, ведь его можно разложить на более простые. Вот они:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30…

Так, у четверки всего три делителя (1, 2 и 4), у шестерки – четыре (1, 2, 3 и 6) и так далее. Обратите внимание, что числа 1 нет и здесь. Математики называют его единицей, числом с уникальным свойством – быть делителем абсолютно любого целого числа.

Каждое составное число может быть представлено в виде произведения простых чисел. Возьмем для примера 120. Можно начать с 120 = 6 ? 20. Но и 6, и 20 – тоже составные. Разложим их сразу на простые: 6 = 2 ? 3, 20 = 2 ? 2 ? 5. Следовательно,

120 = 2 ? 2 ? 2 ? 3 ? 5 = 2?3?5?

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

Здесь-то, кстати, и кроется настоящая причина того, что число 1 не может быть названо простым: будучи простым, оно бы делало эту теорему несостоятельной. Ведь тогда 12, например, можно было бы представить не только как 2 ? 2 ? 3, но и как 1 ? 1 ? 2 ? 2 ? 3, и разложение на простые числа не было бы уникальным.

Однажды разложив число, вы узнаете всю его подноготную. В детстве моим любимым числом была девятка, но с возрастом я узнавал и другие, куда более сложные (вроде ? = 3,14159…, ? = 1,618…, e = 2,71828… или число i, которое не может быть представлено в виде десятичной дроби, о чем мы подробно поговорим в главе 10) и влюблялся в них без памяти. Какое-то время моим фаворитом было 2520 – наименьшее из чисел, которые делятся на все числа от 1 до 10. Вот как оно выглядит при разложении на простые множители:

2520 = 2?3?5?7?

Зная положительные множители, вы можете узнать и положительные делители – вернее, их количество. Так, любой из делителей 2520 должен сводиться к форме 2^a3^b5^c7^d, где a может быть равно 0, 1, 2 или 3 (четыре варианта), b – 0, 1 или 2 (три варианта), а с – 0 или 1 (два варианта). Следовательно, согласно правилу произведения, 2520 имеет 4 ? 3 ? 2 ? 2 = 48 положительных делителей.

Отступление

Из основной теоремы арифметики вытекает любопытное следствие, касающееся простых чисел (вы можете найти его доказательство практически в любом учебнике, причем на первых страницах): если простое число p является делителем произведения двух или более чисел, оно также должно являться делителем одного из них. Например, поскольку

999 999 = 333 ? 3003

кратно 11, то 11 должно быть делителем либо 333, либо 3003 (на деле – только последнего сомножителя: 3003 = 11 ? 273). В случае составных чисел это правило работает не всегда: так, 60 = 6 ? 10 делится на 4, несмотря на то что 4 не является делителем ни 6, ни 10.

Чтобы показать уникальность каждого разложения на множители, пойдем от обратного – предположим, что одно и то же число можно представить несколькими отличными друг от друга произведениями. Допустим, N – наименьшее из чисел, которые можно разложить на простые сомножители двумя разными способами. Скажем,

p₁p₂… p_r = N = q₁q₂… q_s

где все значения p_i и q_j суть простые величины. Так как p₁ очевидно кратно N, оно должно быть делителем одного из значений q_j. Облегчим себе задачу и предположим, что это q₁. Тогда, поскольку q₁ – величина простая, у нас должно получиться q₁ = p₁. Разделив все части уравнения на p₁, приходим к

что означает, что число может быть разложено на множители двумя разными способами, а это противоречит нашему условию, что N есть наименьшее из таких чисел.?

Отступление

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

2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30…

В марсианской системе числа вроде 6 или 10 будут считаться простыми, потому что их нельзя разложить на меньшие четные числа. А отличить простые числа от составных (которые, кстати, чередуются в ряду с завидной регулярностью) не составляет никакого труда: если число делится на 4 без остатка – оно составное (потому что 4k = 2 ? 2k), если не делится – простое (6, 10, 14, 18 и т. д.), ведь его нельзя представить в виде двух меньших четных чисел.

Но давайте посмотрим на число 180:

6 ? 30 = 180 = 10 ? 18

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

В интервале от 1 до 100 насчитывается 25 простых чисел, от 101 до 200 – 21, от 201 до 300 – 16. И тенденция эта сохраняется: чем дальше мы продвигается, тем реже встречаются простые величины (без всякой, впрочем, системы: в промежутке от 301 до 400 их снова 16, а в промежутке от 401 до 500 – 17) – а от 1 000 000 до 1 000 100 мы их найдем всего лишь 6. Объяснение этому вполне очевидно: чем больше число, тем больше потенциальных делителей у него будет.

Давайте попробуем доказать, что есть такие сотни чисел, в которых простых чисел не будет вовсе (и не только сотни – тысячи, миллионы, сколько угодно). Для этого будет достаточно подобрать 99 последовательно идущих друг за другом составных чисел:

100! + 2, 100! + 3, 100! + 4…., 100! + 100

Так как 100! = 100 ? 99 ? 98 ?… ? 3 ? 2 ? 1, его можно разделить на все числа от 2 до 100. Возьмем теперь 100! + 53. Так как 53 – делитель 100! оно должно являться делителем и 100! + 53. Та же логика подсказывает, что при 2 ? k ? 100 100! + k должно быть кратным k, а следовательно, составным.

Отступление

Обратите внимание, что мы пропустили 100! + 1. Впрочем, ничто не мешает нам взять и его. На этот счет существует очень интересная теорема – теорема Вильсона, которая утверждает, что число n является простым тогда и только тогда, когда (n – 1)! + 1 делится на n без остатка. Применим ее к нескольким малым величинам: 1! + 1 = 2, что кратно 2; 2! + 1 = 3, что кратно 3; 3! + 1 = 7, что не кратно 4; 4! + 1 = 25, что кратно 5; 5! + 1 = 121, что не кратно 6; 6! + 1 = 721, что кратно 7; и т. д. Следовательно, поскольку число 101 – простое, согласно теореме Вильсона, 100! + 1 является кратным 101 и потому составным. Значит, промежуток от 100! до 100! + 100 содержит в себе непрерывную последовательность, состоящую из 101 составного числа.

Итак, чем больше числа, тем меньше среди них попадается простых. Вполне логично было бы предположить, что рано или поздно они перестают попадаться вовсе. Но только не в этом случае, как больше 2000 лет назад предупредил нас Евклид. Дерзнем не поверить великому греку на слово и докажем это сами.

Теорема: Количество простых чисел бесконечно.

Доказательство: Предположим обратное – что количество простых чисел конечно. Значит, существует некое наибольшее простое число. Обозначим его литерой P. Возьмем число P! + 1. Так как P! делится на все числа в промежутке от 2 до P, ни одно из них нельзя разделить на P! + 1 без остатка. Следовательно, простой множитель P! + 1 будет больше P, что противоречит нашему условию, что P есть наибольшее простое число.?

И хотя мы никогда не найдем наибольшее простое число, математики и специалисты по вычислительной технике не оставляют попыток зайти в этих поисках все дальше и дальше в бесконечность числового ряда. Самым большим известным науке простым числом на настоящий момент является число, состоящее из 17 425 170 цифр. Чтобы его записать, потребуется примерно сотня томов – каждый объемом не меньше книги, которую вы сейчас держите в руках. Но можно уместить и в одну строку –

2^{57 885 161} – 1

А все благодаря существованию удивительно действенных методов, которые позволяют легко определить, являются ли числа вида 2n – 1 или 2n + 1 простыми.

Отступление

Великий Пьер де Ферма доказал, что если p – это нечетное простое число, то число 2^p–1 – 1 должно быть кратно p. Проверим это на примере нескольких первых нечетных простых чисел. Для 3, 5, 7 и 11 мы видим, что 2? – 1 = 3, что кратно 3; 2⁴ – 1 = 15, что кратно 5; 2⁶ – 1 = 63, что кратно 7; 2¹⁰ – 1 = 1023, что кратно 11. Что касается составных чисел, совершенно ясно, что при четном значении n 2^n–1 – 1 будет нечетным, а потому кратным n быть никак не может. Составные же нечетные, вроде 9, 15 или 21, дают нам 2⁸ – 1 = 255, что не кратно 9; 2¹⁴ – 1 = 16 383, что не кратно 15; 2²⁰ – 1 = 1 048 575, что не кратно 21 (да хотя бы и 3).

Следствием теоремы Ферма является то, что, если при наибольшем значении числа N 2^N–1 – 1 не кратно N, мы можем со стопроцентной уверенностью утверждать, что N не может быть простым, при этом нам даже необязательно знать его множители! Тем не менее это не совсем так: существуют такие составные числа, которые ведут себя абсолютно как простые (и по этой причине называются псевдопростыми). Самый простой пример – 341 = 11 ? 31: 2³⁴⁰ – 1 вполне себе кратно 341. И хотя встречаются такие числа крайне редко, их количество все же бесконечно, а для их определения придуманы специальные методы.

Простые числа активно используются в повседневной жизни – в частности, в вычислительной технике при создании алгоритмов кодирования (на них, например, построена система шифрования с открытым ключом, которая используется при совершении финансовых операций онлайн). В большинстве своем они построены на методах быстрого определения того, является ли то или иное число простым. Жаль только, что нет настолько же эффективных способов быстрого разложения на множители по-настоящему огромных чисел. Так, если я перемножу два случайных тысячезначных числа и скажу вам двухтысячезначный ответ, вы никогда в жизни не сможете найти составляющие его простые величины – ни сами, ни с помощью компьютера (конечно, если этот компьютер не квантовый – а такие собирать пока еще попросту не научились). Зато представляете, насколько надежны коды (вроде алгоритма RSA[17]), в основе которых лежит эта неспособность?

Интерес человечества к простым числам стар, как само человечество. Древние греки называли число, равное сумме его делителей (естественно, за исключением самого этого числа), совершенным. Среди них, например, число 6, сумма делителей которого – 1, 2 и 3 – равна 6. Или 28, получающееся из сложения 1, 2, 4, 7 и 14. Дальше следуют 496 и 8128. Интересно, складываются они в какую-нибудь закономерность? Попробуем разложить их на множители:

Видите закономерность? Первое число – это степень основания 2. Второе – на единицу меньше, чем удвоенная степень основания 2; и при этом оно простое (поэтому здесь и нет 8 ? 15 или, скажем, 32 ? 63: ведь 15 и 63 простыми числами не являются). Закономерность эту можно сформулировать в виде теоремы.

Теорема: Если число 2ⁿ – 1 является простым, число 2^n–1 ? (2ⁿ – 1) будет совершенным.

Отступление

Доказательство: Допустим, что число p = 2ⁿ – 1 – простое. Докажем теперь, что число 2^n–1p – совершенное. Какие величины являются его собственными делителями? Сначала – делители, которые не используют множитель p: 1, 2, 4, 8…., 2^n–1. Все они сводятся к сумме 2ⁿ – 1 = p. Потом – все остальные (за исключением самого 2^n–1p), которые включают в себя множитель p и которые дают в сумме p(1 + 2 + 4 + 8 +… + 2^n–2) = p(2^n–1 – 1). Следовательно, общая сумма всех собственных делителей составит

p + p(2^n–1 – 1) = p(1 + (2^n–1 – 1)) = 2^n–1p

что и требовалось доказать.

Великий Леонард Эйлер доказал, что каждое четное совершенное число может быть сведено к этой форме. Именно это представление помогло определить 48 совершенных четных чисел. Существуют ли в принципе среди совершенных чисел нечетные, не знает никто. Доказано, что если и существуют, то наименьшее из них состоит из более чем трех сотен цифр. Несуществование же их пока что так и не доказано.

С простыми числами связано множество нерешенных математических проблем. Одну из них я уже упоминал: неизвестно, бесконечно ли количество простых чисел Фибоначчи (если помните, мы выяснили, что во всей последовательности всего лишь два полных квадрата чисел – 1 и 144 – и столько же кубов – 1 и 8).

Еще одна проблема – известная как гипотеза Гольдбаха – основана на предположении, что любое четное число больше 2 есть сумма двух простых чисел. Доказать этого никто не смог, однако известно, что, если контрпример и существует, в нем должно быть никак не меньше 19 цифр. (Совсем недавно, в 2013 году, в решении очень похожей проблемы произошел прорыв: перуанец Харальд Хельфготт доказал, что любое нечетное число больше 7 есть сумма как максимум трех нечетных простых чисел.)

А еще есть простые числа-близнецы (парные простые числа) – простые числа, разность между которыми составляет ровно 2: 3 и 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31 и так далее. Единственные «тройняшки» в этом ряду – это 3, 5 и 7. И хотя было доказано (в качестве частного случая теоремы Густава Дирихле[18], что количество простых чисел, заканчивающихся на 1 (а также на 3, 7 или 9), бесконечно, вопрос о том, бесконечно ли количество простых чисел-близнецов, остается открытым.

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

Утверждение: Все положительные целые величины интересны.

Доказательство: Вы, без сомнений, согласитесь, что первые положительные числа не оставляют вас равнодушными. Например, 1 – это самое первое положительное число, 2 – первое четное положительное число, 3 – первое нечетное простое число… Предположим обратное – что совсем не все числа так уж интересны. Тогда есть некая самая первая навевающая скуку величина. Назовем ее N. Но разве самого этого факта недостаточно, чтобы сделать N отличной от всех остальных величин и хотя бы уже поэтому интересной? И разве не доказывает это, что «скучных» чисел попросту не бывает?