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

Избранные задачи Вопрос-Ответ
Вход для наших учеников
Личный номер
Пароль

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

(о факторизации чисел)

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

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

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

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

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


Для иллюстрации применим этот алгоритм к числам 104 и 39:

104 : 39 = 2 (остаток 26);

39 : 26 = 1 (остаток 13);

26 : 13 = 2 (остаток 0).

Ответ: НОД (104, 39) = 13.

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

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

Пусть, например, . Замечаем, что . Устанавливаем по признакам делимости, что не делится на 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. Это даёт ; ; ; . Имеем ; ; .

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

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

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

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


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

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

.
Окончательно: .

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


Упражнения

  1. Найти НОД чисел 80887 и 40091.
  2. Доказать, что имеет только один простой множитель, меньший,
    чем 30. (Воспользоваться числом .)

     

     

  3. Найти все множители числа из задачи 2.
  4. Применить «факторизацию по разности квадратов» к разложению числа 131289 на
    простые множители.
  5. Выполнить «факторизацию по разности квадратов» числа 500207. (Применить
    «уловку» предварительного умножения на 3).
  6. Применяя «факторизацию по разности квадратов» непосредственно к числу , убедитесь в том, что . Сколько потребовалось
    шагов? Зная результат разложения , объясните, почему самым лучшим
    множителем, ускоряющим процесс разложения , оказалось бы число 8? Сколько
    потребуется шагов для разложения числа ?

 

Программная часть/дизайн:
Соловьев П.Н. SPECIALIST® Online Certified

PHP Specialist
Контент:
Серебренникова Л.Г.
Rambler's Top100 Союз образовательных сайтов Яндекс цитирования