Магия математики: Как найти x и зачем это нужно - Артур Бенджамин

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

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

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

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

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

где все значения pi и qj суть простые величины. Так как p1 очевидно кратно N, оно должно быть делителем одного из значений qj. Облегчим себе задачу и предположим, что это q1. Тогда, поскольку q1 – величина простая, у нас должно получиться q1 = p1. Разделив все части уравнения на p1, приходим к

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

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

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

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

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

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

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

Так как 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 цифр. Чтобы его записать, потребуется примерно сотня томов – каждый объемом не меньше книги, которую вы сейчас держите в руках. Но можно уместить и в одну строку –

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

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

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

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