Рудольф Ташнер - Число, пришедшее с холода. Когда математика становится приключением

раз.

Множители перед степенями a выглядят дробями только по видимости; на самом деле это целые числа. Другими словами, знаменатель записанной дроби наверняка является делителем числителя. Тем не менее простое число p , записанное первым, не делится на знаменатель, так как именно в этом и заключается суть простого числа. Поэтому множители, стоящие перед степенями a , начиная с a p — 1и заканчивая a = a 1, являются не только целыми числами, но и числами, кратными простому числу p .

Обобщая, получаем:

( a + 1) p = a p + 1 + …,

причем все числа, скрытые за обозначением …, делятся на простое число p .

Допустим, утверждает далее Ферма, что мы уже знаем, что a p — a без остатка делится на p . Тогда, согласно уравнению

( a + 1) p –( a + 1) = a p + 1 + … — ( a + 1) = a p + 1 + … – a — 1 = a p — a + …

и вследствие того факта, что все числа, скрытые за многоточием, делятся на p , разность ( a + 1) p — ( a + 1) тоже делится на p .

Тем самым Ферма наглядно показал то, что хотел доказать, ибо 1 p — 1, очевидно, делится на p . Проведенное выше рассуждение показывает, что отсюда и 2 p — 2 тоже делится на p . Точно такое же рассуждение доказывает, что и 3 p — 3 тоже делится на p . Точно такое же рассуждение, проведенное еще раз, доказывает, что и 4 p — 4 делится на p . Так можно от каждого числа a , о котором известно, что a p — a делится на p , перейти к следующему числу a + 1 и уже относительно его установить, что ( a + 1) p — ( a + 1) делится без остатка на p .

Доказанный здесь факт называют теоремой Ферма . Это не «большая теорема Ферма», о которой рассказывает Саймон Сингх в своей чудесной книжке «Великая теорема Ферма», а так называемая «малая теорема». Правда, эта теорема вовсе не «малая», скорее она очень даже значительная. Кстати сказать, Ферма ни словом не обмолвился, как он пришел к этой теореме. Только столетие спустя Леонард Эйлер смог доказать, почему эта теорема верна. Если известно, что a p — a = a ( a p — 1— 1) делится на простое число p и если само число a на p не делится, то отсюда следует, что при делении a p — 1 на p необходимо получается остаток, равный единице, потому что если a не делится на p , то a p — 1— 1 должно делиться на p . Это утверждение иногда тоже называют «малой теоремой Ферма».

Например, при делении двенадцатой степени любого, не делящегося на 13 числа получается остаток, равный единице. Или при делении шестнадцатой степени любого, не делящегося на 17 числа получается остаток, равный единице.

Здесь довольно неожиданно снова подходим к методу шифрования Джорджа Смайли: дело в том, что малая теорема Ферма гласит: для каждого, не делящегося на 13 числа a , в частности для a = 7 при делении числа a 12 на 13 получится остаток, равный единице. Малая теорема Ферма гласит также, что — в случае, если a не делится на 17, — шестнадцатая степень числа a 12, то есть число ( a 12) 16 = a 12 × 16 = a 192 делится на число 17 с остатком, равным единице. На 13 это же число тоже делится с остатком, равным единице. То есть при делении степени a 192 на модуль 13 × 17 = 221 мы с гарантией получим остаток, равный единице. Запишем это в виде формулы: a 192 ≡ 1.

Число 192, которое мы получили в результате следующего вычисления: (13 — 1) × (17 — 1) = 12 × 16, столь же секретно, как и извлеченный Тоби Эстерхази из сейфа секретный коэффициент 35. Назовем 192 «секретным модулем».

Умники из Цирка определили, с помощью секретного модуля 192, для степени 11 секретную экспоненту 35. Это число, 35, появляется в силу того, что для него справедливо равенство 35 × 11 = 1 + 2 × 192. Смайли отправил в Цирк из-за железного занавеса радиограмму с числом 184. Это был остаток, который при a = 7 получается от деления a 11 на число 221. В общем виде назовем остаток, который получается при делении a 11 на 221, кодированным, или зашифрованным, числом c . В нашем случае c = 184. Тоби Эстерхази вычисляет остаток от деления c 35 на 221, то есть числа ( a 11) 35на 221. Тем самым он декодирует зашифрованное послание c , превращая его в исходное сообщение a . Почему?

Потому что в ( a 11) 35 число a умножается само на себя 11 × 35 раз, что, в силу того что 35 × 11 = 1 + 2 × 192, означает, что число a суммарно 2 × 192 раз, а затем еще один раз умножается само на себя. Если 192 раза перемножить число a само на себя, после его деления на 221 получится остаток 1. Если то же самое сделать 2 × 192 раз, то получится тот же остаток 1, потому что 1 × 1 = 1. Если же этот остаток еще раз умножить на a , то в итоге получится остаток a × 1. Другими словами, остаток от деления c 35 на модуль 221 равен a × 1, то есть a . Поэтому Тоби, после вычисления остатка от деления 184 35 на 221, узнает о желании Смайли встретиться с агентом номер 7.

Фактически уже за три года до этого британский математик Клиффорд Кристофер Кокс пришел к этой идее. В США, однако, о ней никто не знал, потому что британская секретная служба скрывала ее не только от Советского Союза, но и от Соединенных Штатов.

Это следует из так называемой теоремы о распределении простых чисел, о существовании которой догадывался еще Гаусс: количество простых чисел в ряду до какого-то большого числа x равно приблизительно частному от деления этого числа x на его натуральный логарифм. В свою очередь, этот натуральный логарифм приблизительно равен числу разрядов x , умноженному на 2,3.

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

1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 …

0 0 3 0 0 3 0 0 3

и получает следующую строку:

1 4 4 5 9 5 6 5 6 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8…

То есть отрезок отправленного сообщения будет выглядеть так:

1 4 4 5 9 5 6 5 6.

Смайли, однако, должен понимать, что Карла перехватит оба отправленных им шифрованных сообщения, и его люди напишут их одно под другим: