Факторизация чисел Ферма
Факторизация чисел вида 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}]Даже на весьма слабеньком компьютере построение нужной нам таблицы занимает всего лишь несколько минут.
Да, результат очень даже впечатляет! Но давайте вспомним, что эта таблица нам понадобилась потому, что (с точки зрения компьютера!) у нас не хватило терпения дождаться разложения числа М254 прямым применением функции Factorlnteger. Теперь мы без труда можем написать нужное нам разложение.
M254 = 3x56713727820156410577229101238628035243XMi27.Факторизация чисел вида 2n-7
Наряду с разложениями чисел Мерсенна и чисел вида 2n +1, представляет интерес также факторизация чисел вида 2n -7. Так как эти числа будут натуральными только при n > 2, то в программу нужно вставить начальное значение n, равное 3. Поэтому программа будет иметь следующий вид:
Do[Print[n, ":", Factorlnteger[2 ^ n - 7]], {n, 3.50}]Даже на весьма слабеньком компьютере построение нужной нам таблицы занимает всего лишь несколько секунд.
Как видим, при 3<и<50 среди чисел вида 2n -7 простое только одно, соответствующее значению n = 39. Заметные задержки (несколько секунд) при факторизации чисел такого вида возникают лишь при n>200.