доказать простоту числа

jaril14

как доказать что число Мерсена 2^61-1 простое?

stm7932397

maple

Shini

решето Эратосфена рулит

jaril14

up

Lokomotiv59

Тебе уже ответили. Можно еще воспользоваться алгоритмом Миллера-Рабина, есть его детерминированная модификация. В любом случае вряд ли удастся обойтись без нудных вычислений.
А если не секрет --- откуда такая задача взялась ? Вот доказать простоту числа 2^{2^61-1}-1 --- это я понимаю, важная научная проблема

jaril14

нужно человеческое доказательство без применения вычислительных приемов, насколько я знаю есть алгоримт Лемера для доказательства простоты чисел Мерсена, просто надо было для конкретно этого числа, тема теперь неактуальна, но всё равно было бы интересно узнать как это делается.

Sanych

Нету человеческого доказательства. Просто вычисления, но их не очень много. При должной фанатичности, даже на бумажке делается.
А именно, как написано в Википедии, надо вычислить последовательность остатков 4, 4^2-2=14,14^2-2=194, 194^2-2=... (остатков при делении на 2^61-1, то есть не более чем 19-значных чисел) и убедиться, что на 60 месте в этой последовательности получится 0. Тогда 2^61-1 простое.

jaril14

я уже упоминал этот алгоритм...
это какая должна быть бумажка чтобы можно было на ней произвести 61 возведение чисел в квадрат по модулю числа имеющего 19 цифр в своей записи?
Оставить комментарий
Имя или ник:
Комментарий: