Факторизация целых чисел с помощью функции FactorInteger

В ряде задач очень важно знать, насколько быстро можно разложить целое число на простые множители. По этой причине давайте рассмотрим, какие числа функция FactorInteger может разложить на простые множители за приемлемое время. Конечно, мы не собираемся факторизовать все числа подряд (для этого не хватило бы и многотомного труда), а займемся только классическими последовательностями.

Факторизация чисел десятичная

Факторизация чисел, десятичная запись которых состоит из n единиц

До сих пор мы изучали быстродействие функции FactorInteger на аргументах, близких к 2n. В двоичной системе счисления запись таких чисел содержит много нулей или единиц подряд. Число Мерсенна Mn, например, записывается п единицами, а число 2n+1 — двумя единицами, между которыми стоит л-1 нуль (рассматриваем случай n > 0). Поэтому может показаться, что функция FactorInteger столь эффективна лишь для чисел, которые имеют специальный вид в двоичной системе счисления. Поэтому давайте изучим возможности этой функции по факторизации больших чисел видов, более случайных с точки зрения теории чисел. Попытаемся разложить, например, числа, десятичная запись которых представляет собой повторение одной и той же цифры л раз. Конечно, если n =1, то эта цифра повторяется только один раз, и вопрос о разложении решается в уме. С другой стороны, даже если n> 1, то, разделив такое число на ту цифру, которая повторяется n раз, получим число, десятичная запись которого состоит из л единиц. Так что для факторизации чисел такого вида достаточно иметь таблицу разложения чисел, десятичная запись которых состоит из n единиц. Обозначим это число через 1n. Как задать такое число? Как легко видеть, число, десятичная запись которого состоит из n девяток, равно 10n-1. Разделив это число на 9, получим число, десятичная запись которого состоит из л единиц: (10n-1)/9. Таким образом, мы убедились, что

(10n-1)/9= 1n= 111............................111 («единиц).

Заметим сразу, что такие числа могут быть простыми лишь в том случае, если количество единиц n в записи такого числа — простое. Действительно, если n = m k, то такое число делится как на число, состоящее из т единиц, так и на число, состоящее из k единиц. Короче говоря, от m| n => 1m | 1n. (Убедиться в этом очень легко, мысленно выполнив деление "столбиком".)

Теперь несложно написать нужную нам программу.
Do[Print[n,":",FactorInteger[(10^n-1)/9]],{n,70}]
В пределах таблицы простых чисел совсем немного, они получаются лишь при n = 2, 19 и 23. Поэтому при всех четных n число 1 имеет 11 в качестве простого множителя. Несколько сложнее увидеть, что 3k|n=>3k| 1n. (Например, все числа вида 13m делятся на 3, это следует из школьного признака делимости на 3. Аналогично обстоит дело и с числами вида 19m.) Это следует из того, что 3k|1k . Как видим, используя таблицу факторизации чисел вида 1n, составленную с помощью простой программы, совсем несложно подметить простейшие закономерности в разложении данных чисел.

Факторизация чисел Фибоначчи

Давайте теперь рассмотрим несколько иной пример. Попытаемся факторизовать числа такой последовательности, которая не может рассматриваться как некоторое тривиальное изменение последовательности аn с целым основанием а. В качестве такой последовательности можем выбрать, например, последовательность Фибоначчи. Напомним, что последовательность Фибоначчи рекуррентно определяется так:

F1 = F2 = 1, Fn+2 = Fn+1 +Fn.

Если Fn — простое, то либо n = 4, либо n — простое. Теперь построим таблицу факторизации чисел Фибоначчи.

Для этого напишем программу, в которой предусмотрим вывод не только разложения числа Фибоначчи, но и самого числа.
Do[Print[n,":",Fibonacci[n]], ":", FactorInteger[Fibonacci[n]]],{n,270}]
Данная таблица недаром содержит числа Фибоначчи Р„ для п вплоть до 300. Дело в том, что до 1963 года (а это совсем недавно с точки зрения многотысячелетней истории теории чисел) было известно, что числа ФибоначчиFn являются простыми для n = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47. Упорные же поиски других простых чисел Фибоначчи в то время никаких результатов не дали. Так что с этой точки зрения наша таблица содержит несколько совсем нетривиальных открытий!

Факторизация чисел Мерсенна

Числами Мерсенна, как известно, называются числа Мn = 2n-1. Как следует из формулы разложения двучлена an-bn, они могут быть простыми лишь при простом п. При четном n выражение 2n-1 можно разложить на множители, пользуясь, например, формулой для разности квадратов. Вот первые три числа Мерсенна: М1= 1; M2 == 3; M3 = 7. Дальнейшие вычисления поручим системе Mathematica. Для этого напишем программу для разложения чисел Мерсенна, получающихся при n = 1,2, 3, ..., k.

Сначала давайте решим какой-нибудь конкретный пример. Разложим, например, на множители число M67. Марен Мерсенн в 1644 году высказал мнение, что это число простое. Однако ошибочность этого утверждения была установлена Э. Люка только в 1875 году. Давайте же посмотрим, сколько времени потребуется системе Mathematica, чтобы справиться с более трудной задачей — разложением на простые множители. Итак, вводим запрос Factorlnteger[ 2^67-1 ] . и мгновенно получаем ответ.

{193707721,1}, {761838257287,1}}

Вот это да! Mathematica почти мгновенно сделала то, на что математикам потребовалось затратить 231 год!

Теперь можем смело приступить к написанию программы. В качестве последнего числа, разлагаемого на множители, выберем М257. Именно это число было исследовано М. Б. Крайчиком, который установил, что оно составное. Программа может выглядеть так:
Dо[ Print [n, ": ", Factor-Integer [2^n-1] ],{n,257}]
Однако вывод такой программы выглядит несколько "однолинейно".
1 {} 2 {{3,1}} 3 {{7,1}} 4 {{3,1},{5,1}} 5 {{31,1}} 6 {{3,2},{7,1.}} 7 {{127,1}} 8 {{3,1},{5,1},{17,1}} 9 {{7,1},{73,1}} 10 {{3,1},{11,1},{31,1}} 11 {{23,1},{89,1}} 12 {{3,2},{5,1},{7,1},{13,1}} 13 {{8191,1}} 14 {{3,1},{43,1},{127,1}} 15 {{7,1},{31,1},{151,1}} 16 {{3,1},{5,1},{17,1},{257,1}} 17 {{131071,1}} 18 {{3,3},{7,1},{19,1},{73,1}} 19 {{524287,1}} 20 {{3,1},{5,2},{11,1},(31,1),{41,1}}
Кроме того, он и читается с трудом. Поэтому для преобразования вывода в привычную форму лучше всего использовать макрос, написанный на VBA для Word 2002.
Sub Factorization() i 'Обработка списка множителей
Dim strTemp As String Dim Msg, Style, Title, Help, Ctxt, Response, MyString, R Msg = "Хотите продолжить ?" ' Вопрос Style = vbYesNo + vbCritical + vbDefaultButton2 ' Кнопки Title = "Разложение на множители"' Заголовок окна Response = vbYes ' Пока ошибки не обнаружены Selection.Find.ClearFormatting 'Очистка формата в поле поиска With Selection.Find .Text = "{" ' Что ищем - открывающую скобку .Forward = True .Wrap = wdFindContinue .Format = False .MatchCase = False .MatchWholeWord = False .MatchWildcards = False .MatchSoundsLike = False .MatchAllWordForms = False End With Selection.Find.Execute 'Находим открывающую фигурную скобку списка strTemp = Selection.Text If strTemp = "{" Then ' Если нашли скобку, обрабатываем список Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем скобку Do ' В цикле обрабатываем все элементы списка Response = Multiplier ' Обработка множителя и его показателя If Response = vbYes Then Selection.MoveRight Unit:=wdCharacter, Count:=1, _ Extend:=wdExtend strTemp = Selection.Text ' Выбираем очередной символ If strTemp = "," Then ' Это должна быть запятая Selection.Delete Unit:=wdCharacter, Count:=l ' Удаляем ее Selection.Font.Reset ' Сбрасываем форматирование Selection.InsertSymbol Font:="Symbol", _ CharacterNumber:=-3916, Unicode:=True ' Знак умножения End If ' Запятую заменили знаком умножения Else R = MsgBox("***Ошибка: неправильно записан множитель." _ + Msg, Style, Title) End If Loop While strTemp = "," And (Response = vbYes) Выполняем цикл, пока не обработаем все множители 1 или не обнаружим ошибку • If strTemp = "}" Then ' Список должен заканчиваться закр. скобкой Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем скобку Else Response = MsgBox("***0шибка: в конце списка нет } ... " _ + Msg, Style, Title) If Response = vbYes Then ' Пользователь выбрал Yes (Да) MyString = "Yes" ' Запомним, что выбрал пользователь Else ' Пользователь выбрал No (Нет) MyString = "No" ' Запомним, что выбрал пользователь End If End If End If End Sub Function Multiplier() i ' Обработка множителя (и его степени) Dim strTemp As String Dim Msg, Style, Title, Help, Ctxt, Response, MyString Msg = "Хотите продолжить ?" ' Вопрос к пользователю Style = vbYesNo + vbCritical + vbDefaultButton2' Кнопки Title = "Очередной множитель: степень простого" 'Заголовок окна Response = vbYes ' Пока ошибки не обнаружены ' Selection.MoveRight Unit:=wdCharacter, Count:=l, Extend:=wdExtend strTemp = Selection.Text ' Выбираем очередной символ If strTemp = "{" Then ' Если открывающая скобка - начало множителя Selection.Delete Unit:=wdCharacter, Count:=1 ' Скобку удаляем Selection.MoveRight Unit:=wdWord, Count:=l, Extend:=wdExtend Selection.MoveRight Unit:=wdCharacter, Count:=1 ' Основание Selection.MoveRight Unit:=wdWord, Count:=1, Extend:=wdExtend strTemp = Selection.Text ' Основание отделяется , от показателя If strTemp = "," Then ' Разделитель нашли PowExp ' Обрабатываем показатель Selection.MoveRight Unit:=wdCharacter, Count:=l, _ Extend:=wdExtend strTemp = Selection.Text ' Этот символ завершает множитель If strTemp = "}" Then ' Это должна быть закрывающая скобка Selection.Delete Unit:=wdCharacter, Count:=1 ' удалить ее Else ' Но ведь в конце же должна быть закрывающая скобка Response = MsgBox("***0шибка в сомножителе: нет } ... " _ + Msg, Style, Title) If Response = vbYes Then ' Пользователь выбрал Yes (Да) MyString = "Yes" ' Запомним, что выбрал пользователь Else ' Пользователь выбрал No (Нет) MyString = "No" ' Запомним, что выбрал пользователь End If End If Else ' Иначе - а где же запятая? Response = MsgBox("***0шибка в сомножителе: нет , ... " _ + Msg, Style, Title) If Response = vbYes Then ' Пользователь выбрал Yes (Да) MyString = "Yes" 'Запомним, что выбрал пользователь Else ' Пользователь выбрал No (Нет) MyString = "No" ' Запомним, что выбрал пользователь End If End If Else ' Иначе - а где же открывающая скобка ? Response = MsgBox("***0шибка в сомножителе: нет { ... " _ + Msg, Style, Title) If Response = vbYes Then ' Пользователь выбрал Yes (Да) MyString = "Yes"' Запомним, что выбрал пользователь Else ' Пользователь выбрал No (Нет) MyString = "No" ' Запомним, что выбрал пользователь End If End If Multiplier = Response End Function Sub PowExpO i ' Обработка пokaзaтeля t Dim strTemp As String Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем символ Selection.MoveRight Unit:=wdWord, Count:=l, Extend:=wdExtend strTemp = Selection.Text ' Это и есть показатель If strTemp = "1" Then ' Если показатель равен 1 Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем его Else ' В противном случае форматируем его как надстрочный With Selection.Font .Superscript = True 'Надстрочный End With Selection.MoveRight Unit:=wdCharacter, Count:=1 Selection.Font.Reset 'Восстановить стиль End If End Sub
Этот макрос преобразует разложение
{{3,3}, {5,1}, {7,1}, {13,52},{17,1},{19,551}, {37,1},{73,1},{109,1}, {241,1},{433,1},{38737,1}}
к более привычному виду:
33x5x7xl352xl 7X19S51X37X7 3x109x241x433x38737
Теперь можем воспользоваться созданной программой и составить таблицу разложения чисел Мерсенна на простые множители (табл. Б. 10).

Довольно интересно наблюдать за тем, как Mathematica составляет эту таблицу. Первая сотня чисел Мерсенна разлагается практически мгновенно. Незначительные задержки происходят только на второй сотне. Интересно отметить, что эти задержки в пределах второй сотни происходят и при составных n, т.е. в случаях, когда человек воспользовался бы уже вычисленными ранее разложениями. Это свидетельствует о том, что Mathematica в данном случае не пользуется формулой разности степеней. Впрочем, первая существенная задержка происходит только при значении n = 227 (простое). Однако почти сразу же за ней Mathematica сталкивается с рядом незначительных трудностей, которые она быстро преодолевает, но при n = 251 (простое) происходит вторая существенная задержка. Однако поистине удивительно, что самая существенная задержка происходит, казалось бы, в очень простом случае — при n = 254. Ведь при этом значении и число Мерсенна представляет собой разность квадратов, так что фактически число сразу разлагается на множители, которые только на единицу отличаются от корня квадратного из исходного числа. Так что количество цифр в подлежащих разложению числах фактически на первом же шаге уменьшается вдвое! Кроме того, одно из этих чисел представляет собой число Мерсенна М127, которое уже было разложено на множители ранее (точнее, была установлена его простота). Однако если пропустить это число, то разложения М127 и М256 получаются достаточно быстро.

А вот чтобы на нынешних ПК средней мощности разложить число М. Б. Крайчика (Л/257) прямым применением функции FactorInteger, придется подождать несколько часов.

Давайте теперь обсудим, почему все же для системы Mathematica разложить число Крайчика проще, чем М127. Дело в том, что хотя по формуле разности квадратов M254 = M127х(2127+1), система Mathematica об этом не подозревает, и потому она должна сначала найти множитель M127, а затем доказать его простоту. Кроме того, нужно еще разложить на множители число 2'27+1. Это, правда, чуть легче, поскольку очевидно, что оно делится на 3. Впрочем, необходимость в разложении чисел вида 2"+1 в теории кодирования возникает столь часто, что стоит испробовать возможности системы и в этом случае.

простые, можно сказать, почти

Факторизация чисел вида 2n+1

Среди чисел вида 2n+ 1 простые, можно сказать, почти не встречаются, ведь число такого вида может быть простым только тогда, когда n является степенью двойки: n = 2*. Такие числа называются числами Ферма:

Fn = 22n +1.

Пьер Ферма утверждал, что все такие числа просты. Однако Л. Эйлер установил, что F5= 232+l делится на 641. Давайте попытаемся составить таблицу разложения чисел вида 2"+1 на простые множители. В свое время (70-е годы прошлого столетия) Дональду Кнуту удалось исхитриться и с помощью тождества 2214+1 = (2107-254-Н) (2|07+254-Н) и мощного (для того времени) компьютера факторизовать это число. Давайте попробуем и мы. Вот необходимая программа.
Do[ Print[n,":",FactorInteger[2^n+1]], {n, 214} ]
Даже на весьма слабеньком компьютере построение нужной нам таблицы занимает всего лишь несколько минут .

Да, результат очень даже впечатляет! Но давайте вспомним, что эта таблица нам понадобилась потому, что (с точки зрения компьютера!) у нас не хватило терпения дождаться разложения числа Мг54 прямым применением функции Factorlnteger. Теперь мы без труда можем написать нужное нам разложение.
М254 = 3x56713727820156410577229101238628035243XMi27.

представляет интерес также факторизация чисел

Факторизация чисел вида 2n-7

Наряду с разложениями чисел Мерсенна и чисел вида 2n+1, представляет интерес также факторизация чисел вида 2n7-. Так как эти числа будут натуральными только при n > 2, то в программу нужно вставить начальное значение n, равное 3. Поэтому программа будет иметь следующий вид:
Do[Print[n, ":",Factorlnteger[2^n-7]],{n,3,50}]
Даже на весьма слабеньком компьютере построение нужной нам таблицы занимает всего лишь несколько секунд .

Как видим, при 3<и<50 среди чисел вида 2n-7 простое только одно, соответствующее значению n = 39. Заметные задержки (несколько секунд) при факторизации чисел такого вида возникают лишь при n>200.

следуя логике изучения чисел, близких

Факторизация чисел вида 10n+1

Теперь, следуя логике изучения чисел, близких к 2n, построим таблицу факторизации чисел вида 10n+1. В десятичной системе счисления запись таких чисел начинается и заканчивается единицей, а между этими единицами стоят нули:

10n + 1 = 1000............................00001 (n-1 нулей).

Вспоминая формулы суммы степеней, сразу замечаем, что такие числа могут быть простыми лишь в том случае, если л является степенью двойки, т.е. если n = 2k. (При нечетных и, все такие числа делятся, например, на сумму оснований, т.е. на 11.)

Вот программа, которая строит нужную нам таблицу.
Do[Print[n,":",Factorlnteger[10^n+1]],{n,70}]

Факторизация дробей

Прочитав заголовок, вы, возможно, скажете: "Раскладывать дроби на простые множители? Да как же это?! Такой операции в арифметике нет!". Действительно, такой операции вроде бы и нет, но вспомните, как часто приходится раскладывать на простые множители числитель и знаменатель одной и той же дроби. И чтобы вы не мучились, по отдельности вызывая функцию FactorInteger для числителя и знаменателя, можете вызвать ее для всей дроби. Это ведь так удобно! В каком же виде будет представлено разложение? Почти в том же, что и для целых чисел, но только показатели простых множителей знаменателя будут отрицательными. Вот пример:
Factorlnteger[1952/1921]={{2,5},{17,-1},{61,1},{113,-1}}.
Давайте же теперь испытаем функцию FactorInteger в новой роли:
Do[Print[n,":",Factorlnteger[BernoulliB[n]]], {n,2,102,2}]
Результат, как обычно, представим в виде таблицы. Однако оказывается, что разработанный ранее макрос для преобразования разложения в обычную форму уже не годится. Ведь теперь основания (да и сами показатели) степеней могут быть отрицательными. Поэтому в таких случаях основания нужно взять в круглые скобки. Это учтено в новом макросе.
Sub Factorization() 'Обработка списка множителей Dim strTemp As String Dim Msg, Style, Title, Help, Ctxt, Response, MyString Msg = "Хотите продолжить ?" ' Вопрос Style = vbYesNo + vbCritical + vbDefaultButton2 'Кнопки Title = "Разложение на множители" 'Заголовок окна OptPasteSmartCutPaste = Options. PasteSmartCutPaste Options. PasteSmartCutPaste = False Response = vbYes ' Пока ошибки не обнаружены Selection.Find.ClearFormatting ' Очистка формата в поле поиска With Selection.Find .Text = "{" ' Что ищем - открывающую скобку .Forward = True .Wrap = wdFindContinue .Format = False .MatchCase = False .MatchWholeWord = False - . .MatchWildcards = False .MatchSoundsLike = False .MatchAllWordForm? = False End With Selection.Find.Execute ' Находим открывающую фигурную скобку списка strTemp = Selection.Text If strTemp = "{" Then ' Если нашли скобку, обрабатываем список Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем скобку Do ' В цикле обрабатываем все элементы списка Response = Multiplier ' Обработка множителя и его показателя Selection.MoveRight Unit:=wdCharacter, Count:=1, _ Extend:=wdExtend strTemp = Selection.Text ' Выбираем очередной символ If strTemp = "," Then ' Это должна быть запятая Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем ее Selection.Font.Reset ' Сбрасываем форматирование Selection.InsertSymbol Font:="Symbol", _ CharacterNumber:=-3916, Unicode:=True ' Знак умножения End If ' Запятую заменили знаком умножения Loop While strTemp = "," And (Response = vbYes) ' Выполняем цикл, пока не обработаем все множители ' или не обнаружим ошибку If strTemp = "}" Then ' Список должен заканчиваться ' закрывающейся скобкой (Selection.Delete Unit:=wdCharacter, Count:=1 ' Удаляем скобку Else Response = MsgBox("***0шибка: в конце списка нет } ... " _ + Msg, Style, Title) If Response = vbYes Then ' Пользователь выбрал Yes (Да) MyString = "Yes" ' Запомним, что выбрал пользователь Else ' Пользователь выбрал No (Нет) MyString = "No" . ' Запомним, что выбрал пользователь End If End If End If Options.PasteSmartCutPaste" = OptPasteSmartCutPaste End Sub Function Multiplier() i ' Обработка множителя (и его степени) 1 Макрос записан 26.10.2003 Яков Шмидский t Dim strTemp As String Dim Msg, Style, Title, Help, Ctxt, Response, MyString Msg = "Хотите продолжить ?" ' Вопрос к пользователю Style = vbYesNo + vbCritical + vbDefaultButton2 ' Кнопки Title = "Очередной множитель: степень простого" ' Заголовок окна Response = vbYes ' Пока ошибки не обнаружены strTemp = Selection.Text ' Выбираем очередной символ Selection.MoveRight Unit:=wdCharacter, Count:=l, Extend:=wdExtend If strTemp = "{" Then ' Если отрывающая скобка - начало множителя Selection.Delete Unit:=wdCharacter, Count:=1 ' Скобку удаляем Selection.Extend Character:="," ' Расширили выделение до , Selection.MoveLeft Unit:=wdCharacter, Count:=1, Extend:=wdExtend ' Отменили выделение , BaseRepresent Selection.MoveRight Unit:=wdCharacter, Count:=1 ' Основание Selection.MoveRight Unit:=wdCharacter, Count:=l, Extend:=wdExtend strTemp = Selection.Text ' Основание отделяется , от показателя If strTemp = "," Then ' Разделитель нашли PowExp ' Обрабатываем показатель Selection.MoveRight Unit:=wdCharacter, Count:=l, _ Extend:=wdExtend strTemp = Selection.Text ' Этот символ завершает множитель If strTemp = "}" Then ' Это должна быть закрывающая скобка Selection.Delete Unit:=wdCharacter, Count:=1 ' -Удалить ее Else ' Но ведь в коде же должна быть закрывающая скобка Response = MsgBox("***0шибка в сомножителе: нет } ... " _ + Msg, Style, Title) If Response = vbYes Then ' Пользователь выбрал Yes (Да) MyString = "Yes" ' Запомним, что выбрал пользователь Else' Пользователь выбрал No (Нет) MyString = "No" ' Запомним, что выбрал пользователь End If End If Else ' Иначе - а где же запятая? Response = MsgBox("***0шибка в сомножителе: нет , ... " _ + Msg, Style, Title) If Response = vbYes Then ' Пользователь выбрал Yes (Да) MyString = "Yes" ' Запомним, что выбрал пользователь Else ' Пользователь выбрал No (Нет) MyString = "No" ' Запомним, что выбрал пользователь End If End If End If Multiplier = Response End Function Sub PowExp() t ' Обработка показателя t Dim strTemp As String Selection ..Delete Unit :=wdCharacter, Count :=1 ' Удаляем символ Selection.Extend Character:="}" ' Расширили выделение до } Selection.MoveLeft Unit:=wdCharacter, Count:=1, Extend:=wdExtend ' Отменили выделение } strTemp = Selection .'Text ' Это и есть показатель If strTemp = "1" Then ' Если показатель равен 1 Selection.Delete Unit:=wdCharacter, Count:=l ' Удаляем его Else ' В противном случае форматируем его как надстрочный With Selection.Font .Superscript = True 'Надстрочный End With Selection.MoveRight Unit:=wdCharacter, Count:=1 Selection.Font.Reset 'Восстановить стиль End If End Sub Sub BaseRepresent() Dim strTemp As String strTemp = Selection.Text ' Основание If Not MultiplierQ(strTemp) Then ' Selection.MoveLeft Unit:=wdCharacter, Count:=l ' Selection.InsertBefore "(" ' Перед основанием вставим символ { Selection.InsertAfter ")" ' А после него вставим символ ) End If End Sub Function MultiplierQ(strTemp) ret = True If Left(strTemp, 1) = "-" Then ret = False MultiplierQ = ret End Function
Этот макрос преобразует представление
{{-1,n},{2,-1},{-3,-m},{5,-1},{7,-1},{11,-1}, {13,-1},{31,-1}, {61,-1},{2003,1},{5549927,8},{109317926249509865753025015237911,1}}
в такой более привычный вид.
(-1)nх2-1х(-3)-mх5-1х7-1х11-1х13-1х31-1х 61-1x2003x55499278Х109317926249509865753025015237911
Теперь, пользуясь результатами и макросом, можем составить таблицу . Если нужно разложить только, например, числители, можно воспользоваться следующей программой:
Do:[Print[n,":",Factorlnteger[Numerator[BernoulliB[n]]]],{n,2,102,2}].
Так как это разложение играет чрезвычайно важную роль в доказательстве Последней теоремы Ферма, представим его, как обычно, в виде таблицы.

Эта таблица заслуживает внимания. Прежде всего нужно заметить, она может оказать неоценимую помощь при поиске больших иррегулярных чисел. (Напомню, что простое число р называется регулярным, если на него не делится ни один из числителей чисел Бернулли В2, В4, ..., Вp-3. В противном случае простое число называется иррегулярным.) Иррегулярные простые числа долгое время были причиной ужасных неприятностей для всех, кто занимался доказательством Последней теоремы Ферма. Дело в том, что для регулярных чисел эта теорема была доказана Куммером еще в 1850 году. Это было настоящее торжество ферматистов! Наиболее отчаянные предположили даже, что число иррегулярных чисел конечно, и, таким образом, им оставалось якобы рассмотреть лишь конечное число случаев! Нужно заметить, что их предположение не было лишено оснований. Действительно, в пределах первой сотни есть всего лишь три иррегулярных числа: 37, 59 и 67. (В этом легко убедиться, просмотрев составленную нами таблицу.) Однако в 1915 году Иенсен довольно просто доказал, что множество иррегулярных чисел бесконечно. Тогда-то ферматисты занялись изучением иррегулярных чисел вплотную. В 1965 году Эйхлер существенно продвинулся в поисках доказательства Последней теоремы Ферма, а десять лет спустя, в 1975 году, Брюкнер ввел индекс иррегулярности числа р — количество числителей чисел Бернулли В2, В4, ..., В^, делящихся на р, — и тем самым придал результатам Эйхлера вполне обозримую форму. Понятно, что интерес к таблицам, подобным составленной нами (не без помощи системы Mathematica), значительно возрос. Однако даже в 1985 году, после очередного всплеска интереса к Последней теореме Ферма, когда она была доказана для "почти всех" натуральных показателей, таблица, помещенная в одном из лучших университетских учебников по теории чисел — в учебнике 3. И. Боревича и И. Р. Шафаревича, была доведена лишь до п = 60. Так что едва ли будет преувеличением утверждение, что с помощью системы Mathematica мы составили таблицу, о которой несколько поколений ферматистов могли только мечтать!

Кроме того, эта таблица поможет нам понять, как система Mathematica обращается с дробями. Если число дробное (а именно такими и являются числа Бернулли с четными индексами), то знак дроби относится к числителю. В этом легко убедиться, просмотрев нашу таблицу. Действительно, как мы видели из таблицы разложения чисел Бернулли Вn на простые множители, числа B4n-1 отрицательны, а числа B4n-2 положительны. Точно так же распределены и знаки числителей в таблице разложения числителей чисел Бернулли Вn.

Итак, с помощью функции FactorInteger можем разлагать на простые множители не только натуральные и отрицательные числа, но и дроби, — иными словами, все рациональные числа. Таким образом, кажется, мы научились применять эту функцию ко всем числам, к которым применимо понятие разложения на простые множители. Но возможности этой функции шире. Она умеет еще кое-что. "Как? Неужели... Разве это мыслимо, разлагать на множители комплексные числа?", — возможно, подумаете вы. И не ошибетесь!

Факторизация факториалов

Факториалы являются классическим примером больших чисел. В школе, примерно класса с шестого, учителя плавно готовят детей к тому, что факториалы очень быстро растут, а при изучении комбинаторики говорят, что уже 8! = 40320. Тех же, кто этого не устрашится, на школьном кружке пугают тем, что 100! — невообразимо большое число. Такое большое, что даже вычислить его немыслимо. (Но члены школьного математического кружка обычно знают, что это число вычислил Мольтерер еще до появления ЭВМ.) Дня тех же, кто не убоялся этого числа и (зачастую вопреки устрашениям учителей) преодолел конкурсный отбор в вузы, у профессоров есть очередная страшилка: 1000!. Что-то я не видел профессора, который бы выписал десятичную запись этого числа на доске! Наверное, для профессоров оно и вправду страшное! Но не для нас. Мы его (вместе с системой Mathematica) выпишем раньше, чем профессор успеет моргнуть оком.

Факторизация гауссовых чисел

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

2, 1+2i, i, -i, 1+i, 1-i, 1+7i, 1+555555i, 9999+444i.

На комплексной плоскости гауссовы числа образуют решетку всех точек с целыми координатами. Гауссовы числа называются в честь К. Ф. Гаусса, который обратил на них внимание еще в 1832 году в работе о биквадратичных вычетах. Именно Гаусс понял важность изучения этих чисел и установил их основные свойства.

Как оказалось, множество гауссовых чисел, рассматриваемое с обычными операциями, образует кольцо, являющееся, конечно, подкольцом кольца (даже поля) комплексных чисел. Кольцо целых гауссовых чисел можно рассматривать как расширение кольца целых чисел Z путем присоединения i, поэтому это кольцо обозначается Z[i].

В этом кольце делителями единицы являются лишь +1, -1, i и -i. Так что множество делителей единицы в кольце гауссовых чисел конечно. А потому в этом кольце имеет смысл понятие простого элемента, а, значит, можно выполнять разложение элементов этого кольца на простые множители. Нетрудно доказать, что кольцо целых гауссовых чисел евклидово. Поэтому с точностью до делителей единицы разложение на простые множители в нем единственно. Так что кольцо гауссовых чисел (как и всякое евклидово кольцо) является гауссовым, или факториальным.

Нормой комплексного числа называется квадрат модуля, т.е. квадрат длины отрезка, соединяющего комплексное число с началом координат. Иными словами, это сумма квадратов вещественной и мнимой частей комплексного числа:

N(a+bi) = (а+bi)(а-bi) = a2 +b2.

Нечетное простое число р является простым гауссовым числом тогда и только тогда, когда оно дает в остатке 3 при делении на 4: р = 3 (mod 4). Если же р = 3 (mod 4), то р не является простым в кольце целых гауссовых чисел. Не является простым в кольце целых гауссовых чисел и число 2.

Давайте теперь найдем несколько разложений гауссовых чисел на простые множители.
Factorlnteger[5-51]={(-1,1},{1+i,I},{1+2 i,1},{2+i,1}} FactorInteger[3+1]={{-i,1},(1+i,1},{1+2 1,1)} FactorInteger[-90-180I]={{1+i,2},{1+2 i,2},{2+i,1},{3,2}} Factorlnteger[-182-1261]={{1+i,3},{2 + i,3},{7,1}} FactorInteger[3+I5]={{1+i,1},{4+i,1}} Factorlnteger[777+1111] ={{-1,1},{1+i,1},{1+6 i,l},{2+i,2},{3,l},{6+i,l}} Factorlnteger[153+1 374]={{-i,l},{!+4 i,1},{2+i,1},{4+i,1},{8+7 i,l}} Factorlnteger[7+81]={{7+8i,l}}
Число 7+8 i, как видим, оказалось простым. Заметьте, что Mathematica сама поняла, что разложение нужно выполнять в кольце целых гауссовых чисел. Но как разложить на простые множители в кольце целых гауссовых чисел натуральные числа? Ведь, например, FactorInteger[41] = {{41,1)}.

В подобных случаях, т.е. когда в качестве аргумента функции FactorInteger выступает рациональное вещественное число, а разложить аргумент нужно на простые гауссовы числа, область разложения нужно указать явно. Для этого необходимо с помощью второго аргумента функции FactorInteger установить опцию Gaussianlntegers равной True. Вот несколько примеров, в которых показано, как это делается.
Factorlnteger[41,GaussianIntegers->True]={{-1,1},{4+5i,l},{5+4i,lH FactorInteger[5,GaussianIntegers->True]={{-i,l},{!+2i,i},{2+i,1}} Factorlnteger[2,GaussianIntegers->True]={{-i,1},{1 + i,2}} Factorlnteger[11,GaussianIntegers->True]={{11,1}} FactorInteger[13,GaussianIntegers->True]={{-i,l},{2+3i,l},{3+2 i,l}}
Как видите, ничего сложного!

Факторизация очень больших чисел

Как мы уже видели, функция Factorlnteger вполне справляется с разложением чисел, десятичная запись которых содержит не более 60—70 десятичных знаков (это примерно две сотни двоичных). Хотя именно такие числа чаще всего встречаются на практике, их множество конечно. Дополнение же этого множества до множества натуральных чисел бесконечно! Поэтому иногда приходится раскладывать и числа, содержащие несколько сотен, а то и тысяч десятичных знаков. Конечно, в таких случаях зачастую приходится полагаться на удачу. Однако и здесь может помочь Mathematica. Например, если известно, что некоторое число является большой степенью некоторого основания, то достаточно разложить только основание. Так что этот случай большого числа для процедуры факторизации можно считать тривиальным. Несколько менее тривиальным является случай факториала.

Функция FactorIntegerECM попытка

Функция FactorIntegerECM: попытка факторизации больших чисел Мерсенна

Давайте на примере попытки разложения больших чисел Мерсенна рассмотрим, как Mathematica позволяет приблизиться к решению задачи факторизации очень больших чисел.

Факторизация 317-го числа Мерсенна М317

Конечно, можно попытаться применить функцию Factorlnteger. Но это не даст результата (за приемлемое время). Можно, правда, "попросить" функцию Factorlnteger найти хоть какие-нибудь делители числа Мерсенна М317. Для этого нужно воспользоваться опцией FactorComplete->False.

FactorInteger[M317-1,FactorComplete->False]

Результат будет таким.

FactorInteger::facfn: Unable to factor 28072587476617 «64» 65592773657961.

More...

Чуть ниже будут и найденные множители.
{{9511, 1), {280725874766179960361032187226573 45634038278340298769450465 797600439224658035965592773657961,1}}
Хорошо, конечно, что нашли множитель 9511, но вот второй множитель... Неизвестно, даже простой ли он. Можно, конечно, попытаться повторить процедуру для него, но это ни к чему новому не приведет.
Factorlnteger::facfn: Unable to factor 28072587476617 «64» 65592773657961. More... {{2807258747661799603610 321872265734563403827834 0298769450465797600439 224658035965592773657961,1}}
В этом случае все придется сделать вручную:.. Возможно, вы подумали о формулах сокращенного умножения. Да, действительно, часто они помогают. (Мы в этом уже не раз убеждались.) Но в данном случае 317 — простое число (я специально так подобрал индекс числа Мерсенна), и применить формулы сокращенного умножения просто так, "в лоб", не удастся. Придется использовать другую функцию. Она есть в пакете теории чисел, который загружается так: «NumberTheory' FactorlntegerECM'.

Сама функция называется FactorIntegerECM. Ее первоначальный алгоритм придумал X. Ленстра (Н. W. Lenstra) в 1985 году. В нем используется теория эллиптических кривых. Функция FactorIntegerECM очень эффективна там, где FactorInteger не справляется. Правда, с другой стороны, она не столь услужлива, как FactorInteger. Она находит только один множитель, притом не обязательно простой. К тому же она привередлива: ее поведение не предсказуемо, если в качестве аргумента передать ей простое число. Поэтому предварительно нужно проверить, что аргумент не является простым числом. Это делается с помощью функции PrimeQ.

Давайте теперь попытаемся применить функцию FactorIntegerECM для какого-нибудь небольшого числа, например 91. (Это число, как мы знаем, не простое.)

FactorIntegerECM[91 ]

А вот и результат.

13

Да, найден только один множитель... Остальное приходится делать вручную. Рассмотрим теперь более сложный пример.
m=12 n = Prime[10Am] Prime[10Лт+1]
Вот что получилось:
12 899773470806612917304808883
Теперь давайте разложим п (оно составное, так как является произведением двух последовательных достаточно больших простых чисел).

FactorIntegerECM[n]

И вот один из сомножителей: 29996224275851

Вот еще один пример применения функции FactorIntegerECM.

n=(2^58 - 27) * (2^127 - 1) 4903985730770843887365 5151436140637119954221204852703259

Теперь ищем какой-нибудь делитель этого числа.

288230376151711717

Наконец, освоившись с функцией FactorIntegerECM на этих более или менее простых примерах, можем попытаться применить ее к факторизации числа Мерсенна Мт. Как мы помним, оно имеет делитель 9511. Сначала убедимся, что он простой.
PrimeQ[9511] True
Теперь можем разделить на него число Мерсенна М317.
n=(2Л317-1)/9511 28072587476617996036103218722657345 63403827834029876945046579760043922 4658035965592773657961
После этого нужно убедиться, что это число составное.
PrimeQ[n] False
Значит, можно применить функцию FactorIntegerECM.

m=Factor!ntegerECM[n]

Через 205,375 с (процессор Pentium 2,4 ГГц) получаем один из его делителей:

587492521482839879 Он простой.

PrimeQ[m] True

Поэтому можем заниматься только частным n = n/m.

n=n/m

477837358776284792683873587315

9342707436119775645430680034874628800586

6959

Опять нужно проверить, простое ли оно.

PrimeQ[n]

Эта проверка занимает всего лишь 0,016 с, и оказывается, что оно составное.

False

Значит, можем снова применить функцию FactorIntegerECM.

m=Factor!ntegerECM[n]

На этот раз понадобится 727,047 с, чтобы найти очередной делитель. 4868122671322098041565641

Снова нужно проверить, прост ли найденный делитель. PrimeQ[m]

Эта проверка выполняется пoчти мгновенно, и оказывается, что делитель действительно прост.

True

Значит, снова можем заниматься только частным n= n/m.

n=n/m 9815639231755686605031317440031161584572466128599

Опять нужно проверить, простое ли оно.

PrimeQn]

Эта проверка занимает всего лишь 0,015 с, и оказывается, что найденное частное является простым числом.

PrimeQ[ n] True

Таким образом, мы нашли все простые множители 317-го числа Мерсенна М317 и тем самым разложили этого числового великана на простые множители.
М317 = 9511X587492521482839879X486812267 1322098041565641X981563923175568 6605031317440031161584572466128599
Факторизация 337-го числа Мерсенна М337

Чтобы освоить методику применения функций Factorlnteger и FactorIntegerECM, попробуем разложить на простые множители 337-е число Мерсенна M337. Сначала можно попытаться применить функцию Factorlnteger. Но как и в случае 317-го числа Мерсенна M317, это не даст результата за приемлемое время. Тогда применим функцию Factorlnteger с опцией FactorComplete->False, чтобы найти хоть какие-нибудь делители 337-го числа Мерсенна М337.
Factorlnteger[2^337-1,FactorComplete->False]
Результат будет таким.
Factorlnteger::facfn: Unable to factor 57238939242563 «51» 465444456568561. More...
Зато чуть ниже будут найдены делители.
{{18199, 1}, (2806537,1), (95763203297, 1}, {572389392425637497118853974356 80799950268490508661316904465621201465444456568561, 1}}
Иными словами,
М337=18199X2806537X95763203297X572389392425637 497118853974356807999502 68490508661316904465621201465444456568561
Теперь нужно проверить, просты ли найденные делители.
PrimeQ[18199] True PrimeQ[2806537] True PrimeQ[95763203297] True PrimeQ[5723893924256374971188539743568079 99502684905086613169044656212 01465444456565-61] False
Как видите, все они, за исключением последнего (обозначим его временно через n), самого большого, простые. (Все это заняло менее двух секунд.)

Поскольку 337 — простое число (я опять специально подобрал индекс числа Мерсенна), формулы сокращенного умножения "в лоб" применить не удастся. Но ведь мы можем загрузить пакет теории чисел.

<<NumberTheory"FactorIntegerECM`

Теперь, когда пакет загружен, можно вызвать функцию FactorIntegerECM.

FactorIntegerECM[572389392425637497118

85397435680799950268490508661316 90446562120146544445656561]

Мгновенно находится множитель.

726584894969

Давайте проверим, прост ли он.

PrimeQ[726584894969]

True

Оказывается, прост. Поэтому разделим на найденный множитель полученное на предыдущем шаге число, присвоим частное переменной п и проверим, является ли частное простым числом.
n=57238939242563749711885397435680799950268490 508661316904465621201465 44445656561/726584894969 787780473264667429936124208424161983 11394008068822475527239136925369 PrimeQ[n] True
Поскольку полученное частное является простым числом, мы нашли все простые множители 337-го числа Мерсенна М337 и тем самым разложили и этого числового великана на простые множители.
М337=18199x2806537x95763203297x 726584894969x787780473264667429 93612420 842416198311394008068822475527239136925369
Функция FactorIntegerECM: поиск делителей 5011 -го числа Мерсенна М5011

Функция FactorlntegerECM иногда может находить делители таких чисел, которые можно смело отнести к разряду супервеликанов. Еще в середине прошлого столетия было известно, что 5011-е число Мерсенна Мхи — составное. Вот этот супервеликан.

Для нахождения канонического разложения целых

Резюме

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

Если же функция FactorInteger со своей работой за приемлемое время не справляется, можно сначала найти только те делители, нахождение которых не составит труда для нее, — именно для этого предназначена опция FactorComplete->False. Все же чаще приходится прибегать к имеющейся в пакете теории чисел функции FactorIntegerECM. Однако эта функция за один раз находит только один делитель, притом не обязательно простой. Кроме того, она может зациклиться, если в качестве аргумента получит простое число. Так что перед вызовом этой функции нужно проверить, не является ли ее аргумент простым числом — это делается с помощью функции PrimeQ. (Как правило, функция PrimeQ работает очень быстро.) Получив очередной делитель, число можно разделить на него и проверить, не является ли частное простым числом. Если частное окажется простым числом, то фактически каноническое разложение можно считать полученным, если известны канонические разложения найденных ранее делителей. Если же частное или какой-нибудь делитель окажется числом составным, к нему можно попытаться снова применить функцию FactorIntegerECM. Повторяя эту процедуру достаточное число раз, иногда (для относительно небольших великанов часто) удается найти каноническое разложение.

Если же и этот метод не приводит к успеху, помочь могут различные формулы (например, разложения суммы или разности степеней и т.п.) и предварительно составленные таблицы. Благодаря системе Mathematica к таблицам приходится прибегать существенно реже, чем в докомпьютерную эпоху. Более того, сами таблицы можно составить с помощью программ, написанных на языке программирования, встроенном в систему Mathematica. Однако, как и в эпоху Эйлера и Гаусса, таблицы незаменимы при поиске нетривиальных закономерностей в канонических разложениях чисел того или иного вида. Однако представление, возвращаемое функцией Factorlnteger, несколько "однолинейно" и потому удобно скорее для дальнейшего использования в качестве аргумента других функций, чем для чтения человеком. Хотя это представление система Mathematica может преобразовать в различные форматы, подчас проще написать макрос, преобразующий его в привычный вид.