Алгебра и пакет Mathematica 5
Факторизация чисел вида 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.
