Простые числа

rayev

всегда ли 2^(2^n) простое число. Как доказывается? Желательно написать набросок тут или дать сылку

yulial

Это юмор такой? Типа, математики шутят?

sergo60

Решение: Для n=0 это число простое (=2). Для любого натурального n это число будет составным, так как делится на 2.

satyana

а ты еще больший юморист...

seregen-ka

Как ителлигентно ты объяснил
Другой бы просто дураком обозвал

sergo60

Что просили, то и получили. А про проверку простоты чисел Ферма, могу вечером написать.

sergo60

Если конечно нужны были именно они, а не 2^(2^s)-1, или еще что похлеще.

sergo60

Вспомнил:
Пусть Fn - число Ферма. Fn простое тогда и только тогда, когда 3^Fn-1)/2)=-1(mod Fn)

rayev

Sorry I meant
2^(2^n)+1

yuiop

а это очевидно, что данное сравнение не при всех n выполнено?
я, на самом деле, смутно помню, что вроде бы F_5 составное, но не уверен.

sergo60

Что значит очевидно? Это тест на простоту, критерий. Не все Fn простые, даже наоборот. Не известно ниодного простого числа Ферма кроме F0, F1,F2,F3 и F4. А F5 делится на 641.

koroleff

17, 257, 65537 - простые, а вот следующее уже составное.
Был бы шелл на юних, я б тебе и разложение привёл. тама комманда такая есть factor.

yuiop

просто на вопрос "всегда ли F_n простое" из твоего сравнения нельзя понять ответ. Насколько я понимаю, про числа F_n n>=6 вообще ничего неизвестно, ведь этот критерий на практике тоже сложно применять, числа там очень большие. Или я не прав?

Afonya

А я знаю, а я знаю, это доказал Эйлер, а гипотезу выдвинул Ферма.

ivanovam9

F_6=274177*67280421310721, F_7=59649589127497217*5704689200685129054721....

sergo60

Ты не прав. Уже относительно давно известно для практически всех чисел F5-F21 что они составные, а также их делители.
И ответ на вопрос тест дает. Подставляешь n=5 и получаешь, что F5 составное. Следовательно не все Fn простые.
А в степень возводить по модулю нужно (сделать 2^n раз возведение в квадрат по модулю). Сложность там полиномиальная, с небольшой степенью (относительно длины числа в двоичном представлении, т.е 2^n).
Лучше теста не найдешь.
З.Ы. Вот к примеру пара делителей
n=11 p=319489 Каннингхэм в 1899
n=21 p=4485296422913 Рэтхолл в 1963

rayev

ты уверен?
просто мне казалось вроде в сунце приводили эту формулу, Hазвали формулой гауса и вроде доказали..

Xephon

*6700417=4294967297=2^(2^5)+1
вроде в интернате не доказывают ложных утверждений...

rayev

Oh shit !

sergo60

Это назвали формулой Гаусса 2^(2^n)+1 ?

rayev

МНe так казалось

sergo60

Хотя в полне возможно. Учитывая его теорему, что любой правильный многоугольник с числом сторон Fn можно построить с помощью лишь циркуля и линейки.
P.S. Если ты не знал, то числа вида 2^(2^n)+1 в народе зовутся числами Ферма.

rayev

okey
a kakije u nih prikol'nyje svojstva?

sergo60

Написал же.
Любой правильный многоугольник с числом сторон Fn можно построить с помощью лишь циркуля и линейки.
Fn простое тогда и только тогда, когда 3^Fn-1)/2)=-1(mod Fn)

rayev

Pon'atno:(
Vsem spasibo

bmv007

Есть сайт в инете, посвященный числам Ферма:
http://www.fermatsearch.org

koroleff

>Любой правильный многоугольник с числом сторон Fn можно построить с помощью лишь циркуля и линейки.
Тогда и только тогда, когда Fn простое.

Xephon

это ты, Леха, прогоняешь
19-угольник нельзя построить

sergo60

Чему ж равно n, если Fn=19 ?

Xephon

загнался я - невнимательно прочел
думал, что он пишет для любого простого числа, не только из класса чисел Ферма

rayev

а есть формула которая дает простыe числа?
не все а хотьа бы половину
Оставить комментарий
Имя или ник:
Комментарий: