Магия математики. Как найти x и зачем это нужно

Отступление

Великий Пьер де Ферма доказал, что если 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) будет совершенным.