новое решение сравнения 2^n = 3 (mod n)

[megamix62]

Из $(p,a,m)$ Вы искали только по $a$
т.е $a=(4700063497, 3468371109448915 , 10991007971508067)$ или по другому ?

[dmd]

Да, в этой проверке линий Крампа я не строил. Шёл по простым и составным подходящим числам, как рекомендовал Руст, это можно видеть из кода программы.

[megamix62]

dmd в сообщении #655216 писал(а):

Да, в этой проверке линий Крампа я не строил. Шёл по простым и составным подходящим числам, как рекомендовал Руст, это можно видеть из кода программы.

По пробуй пройтись по $a$.

Если можешь выставь файл для $p>10^10 $

[megamix62]

dmd в сообщении #75306 писал(а):

Известно ли в рамках этой задачи, что линию до потенциального решения можно строить не только от одного подходящего простого, но и от двух, и от N подходящих простых? При этом количество шагов, которые нужно вышагать по линии в конкретном диапазоне возможных решений, уменьшается на порядки. И еще из этого следует, что не все сочетания подходящих простых могут участвовать в решении. Например, 5 и 71 не могут вместе участвовать в решении.

Почему 5 и 71 не могут вместе участвовать в решении.

-- 12.12.2012, 21:00 --

dmd в сообщении #79261 писал(а):

Теперь у меня такой Из найденных таковы все решения кроме $23333 \cdot 205319 \cdot1746169$, которое равно "нулёвошаговому" $a$, вычисленному от двух простых 23333 и 205319.

Можна подробно обьяснить, которое равно "нулёвошаговому" $a$, вычисленному от двух простых 23333 и 205319....

[megamix62]

Теорема. Сравнения $2^n = 3 (\mod n)$ имеет решение тогда и только тогда, когда $n == 1 \ , 19 (\mod 24)$. ( $n == 1 (\mod 6)$)


Следствие. Если $m=2^n - 3 (\mod n)$, то $2^m \ne 3 (\mod m)$ .
Д-во вытекает из того что $2^n - 3 = -1 (\mod 6)$ и выше указанной теоремы .

[dmd]

Условие Маковского равносильно следующему. Любое подходящее натуральное обязано быть $\pm 1 \pmod {24}$ либо $\pm 5 \pmod {24}$. Это условие перед всеми остальными значительно убыстряет процесс формирования подходящих.

[maxal]

dmd в сообщении #761238 писал(а):

Условие Маковского равносильно следующему. Любое подходящее натуральное обязано быть $\pm 1 \pmod {24}$ либо $\pm 5 \pmod {24}$. Это условие перед всеми остальными значительно убыстряет процесс формирования подходящих.

Ну так вы уже по сути использовали это условие, когда проверяли символ Кронекера тут:
post660975.html#p660975

[dmd]

Да, теперь понимаю. Тут акцент на оптимальности алгоритма. У меня символ Кронекера проверялся "внутри". Теперь очевидно, что условие Маковского должно стоять первым.

[dmd]

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

Ну так вы уже по сути использовали это условие, когда проверяли символ Кронекера тут:
post660975.html#p660975

Хотя нет, ещё раз внимательно посмотрел и теперь не понимаю, почему Вы сослались на то условие. Составные числа, которые я там привёл (296419, 316483, 497059, 724147), по условию Маковского подходящи. Они не подходящи по условию maxal-а. Т.е. это два разных условия. Второе дополняет первое, но не заменяет.

[dmd]

Все числа условию maxal-а, начиная с 1489, отбраковываются по китайской теореме об остатках. $chinese(k\pmod h,\pm1||\pm5 \pmod {24})$ должно иметь решение.

[maxal]

dmd в сообщении #763986 писал(а):

Все числа условию maxal-а, начиная с 1489, отбраковываются по китайской теореме об остатках. $chinese(k\pmod h,\pm1||\pm5 \pmod {24})$ должно иметь решение.

Все так, только это мы уже обсуждали: post51861.html#p51861

[Elek]

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

Отыскал новое решение сравнения $2^n\equiv 3\pmod{n}.$ А именно:

$$n = 3468371109448915$$

Таким образом, общее количество известных решений увеличивается до 4-х. Три других решения перечислены на MathWorld.

Занимаетесь ерундой как и остальные "Фермисты", занялись-бы лучше нормальными проблемами, да наверно мозгов не хватит. Только и можете выпендриваться здесь. А по конкретике: если, предположим, число 2 возвести в некую степень n, то оно наверняка будет больше числа определяющую саму степень n - на сколько дело подбора под конкретную степенью И методов такого подбора бесчисленное множество, так-же как числовых решений.
Великая теорема Ферма не-только доказана, но и уточнена, и это только для того что-б вы все занялись наконец-то насущными проблемами ЖИЗНИ!!! Прекратите заниматься ерундой!!!

[Deggial]

Elek, однодневный бан, за бессодержательное сообщение, флейм и переход на личности участников.

[dmd]

Ещё одна попытка улучшить программу сбора подходящих чисел:

(код)

zsearch(p:int, Y:vec)=
{
local(j, i1, i2, it, t):int;
if(p<5, j= 0:int,
 i1= 1:int; i2= (#Y):int; t= -1:int;
 while(p!=t,
  it= ((i2+i1)\2):int; t= Y[it]:int;
  if(p<t, i2= (it-1):int,
   if(p>t, i1= (it+1):int,
    j= it:int; break
   )
  );
  if((i1>i2), j= 0:int; break)
 )
);
return(j:int)
};


pkh()=
{
local(Z, w):vec;
local(L, n, n24, g, i, j, k, h, h3, a, m, a1, m1, a2, m2, d1, d2):int;
local(s):bool;

Z= matrix(0, 3):vec;
\\Z= read("pkh6.dbt"):vec;
L= (#Z~):int;
if(L==0, n= (5):int, n= (Z[L,1]+2):int);

while(n < 10^6,

 if(n%3, if(n%7, if(n%11, if(n%13, if(n%17, if(n%31, if(n%37, if(n%41, if(n%43, if(n%59, if(n%61, if(n%67, if(n%73, if(n%79, if(n%83, if(n%89,
 n24= (n%24):int;
 if((n24==1)||(n24==5)||(n24==19)||(n24==23), if(issquarefree(n),

  s= 1:bool; g= 1:int;

  if(isprime(n),

   h= znorder(Mod(2, n)):int; h3= znorder(Mod(3, n)):int;
   if(!(h%h3),
    k= znlog(3, Mod(2, n), h);
    g= (h/h3):int;
    if(g-1,
     i= zsearch(g, Z[,1]):int;
     if(i,
      a1= (n*k):int; m1= (n*h):int;
      a2= (g*Z[i,2]):int; m2= (g*Z[i,3]):int;
      ,
      s= 0:bool
     )
    )
    ,
    s= 0:bool
   )

   ,

   w= divisors(n):vec;
   d1= w[2]:int;
   i= zsearch(d1, Z[,1]):int;
   if(i,
    d2= w[#w-1]:int;
    j= zsearch(d2, Z[,1]):int;
    if(j,
     a1= (d1*Z[i,2]):int; m1= (d1*Z[i,3]):int;
     a2= (d2*Z[j,2]):int; m2= (d2*Z[j,3]):int;
     g= 2:int;
     ,
     s= 0:bool
    )
    ,
    s= 0:bool
   )

  );

  if(s,
   if(g-1,
    a= lift(trap(, 0, chinese(Mod(a1, m1), Mod(a2, m2)))):int;
    if(a, m= lcm(m1, m2); k= (a/n):int; h= (m/n):int, s= 0:bool)
   )
  );

  if(s, if((!(h%24))&&(kronecker(6, k%24)==-1), if(g-1, print(n)), Z= concat(Z, [n,k,h])))

 ))
 ))))))))))))))));

 n+=2
);

write("pkh.dbt", Z); print(); print(#Z~);
};

Из первого миллиона отфильтровываются 35388 подходящих чисел.

[dmd]

Насколько удачна такая стратегия?


Будем строить линии Крампа от составных чисел, отобранных из общей базы подходящих по следующей схеме:

1) $h$ таких составных подходящих должен делиться на $24$.
2) $k$ должен быть $1||5||19||23\pmod{24}$.
3) пусть $n$ - составное подходящее, удовлетворяющее первым двум пунктам;
$b$ - максимальный простой делитель $n$;
$k_b$ - минимальное решение $2^{k_b} \equiv 3\pmod{b}$.
Тогда чтоб составное $n$ было удачным подходящим должно выполняться условие $2^{k_b} \equiv 3\pmod{n}$.
4) Шагая $i$ шагов по линии Крампа будем искать такое простое $p=k+ih$, чтобы выполнялось исходное условие задачи $2^{np} \equiv 3\pmod{np}$.


Три решения из известных пяти удовлетворяют этой схеме.
Для составного $1482839=97*15287$ условие пункта 3) есть $2^{7219} \equiv 3\pmod{1482839}$. Искомое простое $7412138453$ находится за 20204 шагов.
Для составного $3294605=5*97*6793$ условие пункта 3) $2^{1027} \equiv 3\pmod{3294605}$. Простое $1052742623$ находится за 77498 шагов.
Для составного $485=5*97$ из решения Монтгомери условие пункта 3) $2^{19} \equiv 3\pmod{485}$.

(фильтрация удачных составных)

nkh()=
{
local(Y, Z, w):vec;
local(L, n, h, k, k24, b, kb):int;

Z= read("pkh78.dbt"):vec;
L= (#Z~):int;
Y= matrix(0, 3):vec;
for(i=1, L,
 n= Z[i,1]:int;
 if(!isprime(n),
  h= Z[i,3]:int;
  if(!(h%24),
   k= Z[i,2]:int;
   k24= (k%24):int;
   if((k24==1)||(k24==5)||(k24==19)||(k24==23),
    w= factorint(n):vec;
    b= w[#w~,1]:int;
    kb= znlog(3, Mod(2, b), znorder(Mod(2, b))):int;
    if(lift(Mod(2,n)^kb)==3,
     Y= concat(Y, [n,k,h])
    )
   )
  )
 )
);
write("nkh.dbt", Y); print(#Y~)
};

Из первых $8*10^7$ натуральных у меня отобралось около 2200000 простых и составных подходящих чисел. А из них удачных составных - всего около 3000 штук.


Условие пункта 3) - объяснимая закономерность, или случайное совпадение? Если не случайное, то можно ли усилить это наблюдение?