Доказать, что число ((2^31) - 1) простое

Abdim59

как?

kiritsev

communique:~$ echo $[2**31-1] | factor
2147483647: 2147483647
оно простое.

Abdim59

communique:~$ echo $[2**31-1] | factor
2147483647: 2147483647
нифига не понял....

mtk79

ну это, типа, намек на то, что, будучи засунутым в мощную программу по поиску делителей, отличных от 1, получилося только оно самое.
А вообще, если есть время, можно поиграться
а) с двоичными числами
б) с индукцией, учитывая, что 31=2^5-1.Так, чтобы 2^31-1 являлось бы частным случаем

Focz

б)
Наврядли это поможет, учитывая что среди чисел вида 2^(2^n-1) - 1 большинство составных.

Perce

Можно воспользоваться каким-нибудь алгоритмом для проверки простоты числа. Если банальный перебор делителей не устраивает, то есть более продвинутые алгоритмы.
Adleman L. M., Pomerance C., Rumely R.S. On distinguishing prime numbers from composite numbers // Annals of Math. 117, 1983. p.173-206
Сложность этого алгоритма (ln N)^{c ln ln ln N}, c=const>0

Abdim59

надо доказать простоту на листе бумаги.
вот.
То бишь нужна не проверка простоты, а доказательство

traffic_speed

идея- составить разность между этим числом и ближайшим к нему числом Ферма(заведомо составным)

kachokslava

какой базой располагаем?
ибо для обоснования алгоритма из анналов может потребоваться гораздо больше, чем листок бумаги
да, если "с" в алгоритме из анналов хотя бы >1.8, то количество действий ~ 20^2 = 400. уместится на бумажку?

Abdim59

шутку понял - смешно.
А по делу что-нибудь есть?

traffic_speed

мой пост видел? он по делу был...

Abdim59

твой видел, спасибо, попробуем

z731a



То бишь нужна не проверка простоты, а доказательство
проверка - это строгое доказательство

Razigel

Нужно док-во без использования компутера.

Perce

Вариант 1. Ищем доказательство Эйлера. В то время компьютеров точно не было.
Вариант 2. Смотрим в сторону Lucas-Lehmer Test. Будет не очень легко без компьютера, но при желании осилить вычисления можно

iri3955

Пусть оно делится на p - простое. Считаем, что p < 2^16 = 65536.
Тогда 2^31 = 1 (mod p)
значит 31|(p-1 то бишь p = 31n + 1.
n + 1 не делится на 2,3,5
т.е. n + 1 = 1,7,11,13,17,19,23,29 (mod 30)
Итого примерно 70 * 8 чисел проверить на простоту, в случае простого - джелить
Может, ещё как уменьшить можно
Оставить комментарий
Имя или ник:
Комментарий: