ОЛ ВЗМШ при МГУ: Отделение математики

Так или не так действовал Ферма? (Б. А. Кордемский)

С именем знаменитого Пьера Ферма связано много тайн. Однажды он получил письмо с вопросом: «Является ли простым число 100895598169?» Ферма незамедлительно ответил, что это двенадцатизначное число является произведением двух простых чисел: 898423 и 112303. Способ исследования числа он не раскрыл.

Отыскание простых множителей натурального числа называют для краткости "факторизацией" ("фактор", значит - множитель, составная часть; в этом последнем смысле слово обычно и употребляется). Даже с такими помощниками, как электронные

вычислительные машины, факторизация больших чисел - чрезвычайно трудоёмкая задача, тем более трудно сделать это «ручным способом». Несколько первых простых чисел (2, 3, 5, 7, 11, ...) легко проверяются на их пригодность в качестве возможных множителей испытуемого числа - по известным признакам делимости на эти числа. Упрощает вычисления и знание признаков делимости на какие-либо из последующих простых чисел.

Ясно также, что для всякого заданного числа достаточно испытать в качестве возможных множителей простые числа, меньшие, чем . Действительно, если у числа есть множитель , то ему соответствует, как результат деления на , и некоторый множитель, меньший, чем .

Как приём факторизации можно использовать известный алгоритм Евклида для отыскания наибольшего общего делителя (НОД) двух чисел. Состоит он, как вы, быть может, помните, в следующем: находим остаток от деления большего числа на меньшее, затем находим остаток от деления предшествующего делителя на , затем остаток от деления на и т.д. Последний не равный нулю остаток (он
непременно существует, поскольку, числа ri убывают) и есть НОД заданных чисел (если он равен 1, то они взаимно просты).

Как же применить алгоритм Евклида к факторизации чисел?

Для выявления простых множителей числа образуем другое число - произведение всех простых чисел от наименьшего из «подозреваемых» множителей
числа до наибольшего среди всех простых, меньших, чем . К этим числам и мы и применим алгоритм Евклида.

Пусть, например, . Замечаем, что . Устанавливаем по признакам делимости, что не делится на 3, 7, 11, 13. Кроме того, сразу видно, что 851 при делении на 17 даёт в остатке 1. Остаётся испытать делимость на 19, 23 и 29. Для такого небольшого числа, как 851, это легко сделать прямым делением на каждый из предполагаемых множителей. Но для уяснения метода поступим так, как было бы целесообразно действовать в случае большого числа.

Образуем . Далее, 12673 : 851 = 14 (остаток 759), 851 : 759 = 1 (остаток 92); 759 : 92 = 8 (остаток 23); 92 : 23 = 4 (остаток 0).

Число 23 есть НОД чисел и и, следовательно, один из множителей числа 851. Деля 851 на 23, получаем 37 - число простое.

Факторизация числа 851 окончена: 851 = 23·37.

Для числа, предложенного Ферма, аналогичные вычисления длились бы значительно дольше. (Попробуйте!) Похоже, что сам Ферма считал иначе. Но как?

На подступах к разгадке?

В одной из современных математических книг высказано предположение, что,  по-видимому, «некоторые математики XVII века, потратившие много усилий на  разработку теории чисел, владели незнакомыми нам способами узнавать простые  числа». Но так как мастера-вычислители XVII века не раскрыли потомкам своих  секретов факторизации чисел, то естественно, что способы, изобретённые позже,  могли оказаться и переоткрытиями.

Ферма - один из создателей теории чисел - в своих вычислениях пользовался  самыми разнообразными свойствами чисел. В частности, он, несомненно, знал, что  всякое нечётное число (равно как и всякое чётное, кратное 4) можно  представить в виде разности квадратов двух целых чисел и :

.

Если - простое число, то , , разложение единственно и не даёт иных сомножителей, кроме и 1. Если же - составное, то найдётся разложение , которое даёт хотя бы одну пару множителей, отличных от и 1.

Например, простое число 17 имеет только одно представление в виде разности  квадратов, а именно ; составное же число 203  имеет два таких представления: и .

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

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

Для числа : ; ;  ; имеем -  оба множителя - простые числа. Заметим, попутно, что оба они близки по величине  один к другому и, следовательно, к . В этом - причина краткости  пути к успеху.

Для числа ближайший избыточный квадрат . Вычисляем

;

;

;

;

. . . . . . . . . . . . . . . . . . . . . . . . .

.

Следовательно, .

Успех достигнут только на седьмой попытке. Сравнивая множители числа 689, мы  замечаем, что они сильно различаются по величине, что и вызвало удлинение нашей  процедуры.

Возможная уловка

В таком случае применим хитрость: начнём всё снова, предварительно умножив  заданное N, скажем на 3 (сохраняя тем самым нечётность). Это увеличит меньший из  двух сомножителей числа в 3 раза и сделает величины сомножителей числа  более близкими между собой, а, следовательно, и к .

А если заранее преоложить ещё более значительное различие между  сомножителями числа , то можно умножить его сразу на 5, 7 или 8 (в  последнем случае образуется число чётное, но представимое разностью квадратов
целых чисел). Умножение на 2 в любом случае было бы непригодным, а на 4 -  бесполезным. Докажите это самостоятельно.

Вернёмся к числу и применим в качестве «уловки» умножение на 5. Это даёт ; ; ; . Имеем ; ; .

Успех с одной попытки, а не с семи, как прежде.

Может быть, так и действовал Ферма?

Имеем . Ищем наименьшее число, квадрат которого больше,
чем :

(с избытком).

Далее: . Хотя получившаяся разность и не является  квадратом, продолжать применение алгоритма излишне: дерзость вознаграждена  неожиданным сюрпризом - общим множителем 898424! Разложение числа   обеспечивается теперь простым вынесением общего множителя за скобки:

.

...Так ли всё происходило в «лаборатории» Ферма или как-нибудь иначе -  сведений нигде нет; но в любом случае наше совместное гипотетическое  «путешествие» в прошлое с позиций настоящего, было, надеюсь, для читателя не
бесполезным.