Поиск простых чисел

[megamix62]

maxal в сообщении #571419 писал(а):

Сомневаюсь, что оно работает в обратную сторону.
Если обобщить, то утверждение для нечетного $n$ (пусть некратного 3 и 5) выглядит так:
$m$ - простое тогда и только тогда, когда

$$F_{2m+1} \equiv \frac{3+\left(\frac{5}{m}\right)}2 \pmod{m}.$$

Для простых $n$ это действительно так, но вот для составных есть контрпримеры типа $n=77$. Впролне вероятно, что для $m$ вида $\frac{3^n-1}{2}$ тоже есть контрпримеры, только найти их сложнее.

число Ферма $F_{n}$ является простым тогда и только тогда, когда $3^{(F_{n}-1)/2}=-1\pmod{F_{n}}$.
Число 3 в тесте Пепина может быть заменено на 5, 6, 7 или 10 (последовательность A129802 в OEIS), которые также являются первообразными корнями по модулю каждого простого числа Ферма.

[yk2ru]

megamix62 в сообщении #581798 писал(а):

число Ферма является простым тогда и только тогда, ...

В процитированном вами говорилось о числах Фибоначчи, а не Ферма.

[dmd]

yk2ru в сообщении #570788 писал(а):

Аналог теста Люка-Лемера для чисел вида $Q_n=\frac{3^n-1}{2}$
$(S_n} - A) \mod {Q_n} = 0$ где $S_1 = 2$ и $S_{k+1} = S_k(5S_k^2-3)$
$A = 1$ для $n = 4m + 3$ и $A = 2$ для $n = 4m + 1$
Не скажу, что на 100 процентов тест правильный, но вроде бы для первых 10 чисел n всевдопростых нет.
Вот эти числа $n: 3, 7, 13, 71, 103, 541, 1091, 1367, 1627, 4177$
Далее не пробовал, так как мой комп не настолько мощный.

Еще условие для простых из этой последовательности A028491:

Пусть $p$ - простое, и $T=\frac{3^p-1}{2}$. Тогда если выполняется $2^\frac{T-1}{2p}\equiv \pm 3^x \pmod T$, где $x$ - некое натуральное $<p$, то $T$ - число простое либо псевдопростое.

a028491()=
{
forprime(p=3, 5000,
 T= (3^p-1)/2;
 s= (T-1)/2/p;
 r= lift(Mod(2,T)^s);
 s= lift(-Mod(2,T)^s);
 if((r==3^valuation(r,3))||(s==3^valuation(s,3)), print(p))
)
};

[dmd]

yk2ru, maxal

А как Ваш тест правильно закодировать?

Если буквально воспроизвести

ykmax()=
{
forprime(p=3, 2000,
 T= (3^p-1)/2;
\\ F= fibonacci(3^p);
 F=2; for(i=2,p, F= F*(5*F^2-3));
 q= p%4;
 A= lift(Mod(F,T));
 if(((q==3)&&(A==1))||((q==1)&&(A==2)), print(p))
)
};

то это слишком тяжелый код получается.

[maxal]

dmd
сделайте так - будет быстрее:

F=Mod(2,T); for(i=2,p, F *= 5*F^2-3);

[dmd]

Простые Вагстафа (A000978) подчиняются аналогичному условию $3^\frac{T-1}{2p}\equiv \pm 2^x \pmod T$

a000978()=
{
forprime(p=5, 3000,
 T= (2^p+1)/3;
 s= (T-1)/2/p;
 s= Mod(3,T)^s;
 r= lift(s); s= lift(-s);
 if((r==2^valuation(r,2))||(s==2^valuation(s,2)), print(p))
)
};

Интересно, что последовательность A086218 не укладывается в эту схему, и она очень редкая (короткая?).

[megamix62]

Есть ли такая теорема ?
Если $P=2\cdot 3\cdot 5\cdot 7...P_{K}+1$ - простое,тогда $2\cdot 3\cdot 5\cdot 7...\cdot P_{K}-1$- простое и наоборот.

-- 20.06.2012, 13:06 --

yk2ru в сообщении #581895 писал(а):

число Ферма

cмотрите:
http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 0%BD%D0%B0

[Sonic86]

megamix62 в сообщении #587276 писал(а):

Есть ли такая теорема ?
Если $P=2\cdot 3\cdot 5\cdot 7...P_{K}+1$ - простое,тогда $2\cdot 3\cdot 5\cdot 7...\cdot P_{K}-1$- простое и наоборот.

Это просто неверное высказывание. При $K=1$, например, фигня получается. При $K=4$ имеем простое $211$ и составное $209=11\cdot 19$.

[lim0n]

megamix62 в сообщении #587276 писал(а):

Есть ли такая теорема ?
Если $P=2\cdot 3\cdot 5\cdot 7...P_{K}+1$ - простое ...

А оно всегда простое, см. Евклид, доказательство бесконечности множества простых чисел.

[vorvalm]

$\prod_2^{p_r} p_r\pm 1$ всегда взаимно простое с $\prod p_r$ и только иногда простое.

[Droog_Andrey]

http://primes.utm.edu/top20/page.php?id=5

[Sonic86]

lim0n в сообщении #587290 писал(а):

megamix62 писал(а):

Есть ли такая теорема ?
Если $P=2\cdot 3\cdot 5\cdot 7...P_{K}+1$ - простое ...

А оно всегда простое, см. Евклид, доказательство бесконечности множества простых чисел.

Это очевидно неверно. Вообще, доказательства от противного в частностях ничего не утверждают, исключая лишь само утверждение теоремы, если они используют в построении отрицание верного утверждения

[dmd]

Верно ли?

Для чисел Ферма $F_p$, где $p$ из последовательности A019434, делителями $F_p-2$ являются строго числа $F_n$ из последовательности A000215.

[dmd]

Или сильнее?

Для чисел $F_n$ делителями $F_n-2$ являются строго числа $F_n$.

[dmd]

Иначе говоря $F_n=\prod_0^{n-1}F_i+2$.


Возможно для простых Ферма $F=2^{2^n}+1$ справедливо соотношение $3^\frac{F-1}{2^{n+1}}\equiv -2^x \pmod F$, где $x<2^n$.