Старый сюжет (IMO 1988, Problem 6)

[maxal]

nnosipov в сообщении #1390528 писал(а):

maxal
Кажется, дошло: дело в наличии рациональных решений (принцип Хассе ведь?). Если так, то есть быстрая проверка с помощью критерия Лежандра, которая позволит продолжить последовательность dmd.

Не совсем так. Например, для $k=10$ тоже есть рациональные решения.

-- Wed May 01, 2019 04:09:44 --

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

Но почему-то отсеились 265, 436, 820, которые были кандидатами после численной проверки в Вольфраме.

На каком этапе отсеялись?

[nnosipov]

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

Так фильтровать будет правильно?

Не знаю. Символ Кронекера уже в деле ...

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

Не совсем так.

Спасибо. Похоже, не все так просто.

Пока у меня ответа нет (и не было изначально) на вопрос, как находить те $k$, для которых указанное выше сравнение разрешимо для любых $m$. Будем думать.

[dmd]

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

На каком этапе отсеялись?

на этом:

     for(i=1, #S~,

      m= S[i,1]; p= polrootsmod('X^2 - f, m); if(!#p, s= 0; break())

     );

если закоментарить этот кусок, т.е. проверку по простым в знаменателе a, то вывод такой:

? nno2()
20, 52, 65, 73, 148, 160, 164, 241, 244, 265, 281, 340, 416, 436, 452, 505, 569, 577, 58
0, 601, 641, 720, 724, 745, 801, 820, 848, 865, 884, 916, 929, 976,

[dmd]

Видимо оно было не верно? В Вольфраме то по модулю можно проверить выражение от любого набора переменных

например Solve[a^2 + b^2 == 160 (a b + 1), {}, Modulus -> 3]

но polrootsmod в pari/gp только для одной переменной. Как в pari/gp по модулю простого проверить разрешимость уравнения двух переменных?

[maxal]

dmd, почему просто не перебрать всех кандидатов на роль решений?

[nnosipov]

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

Видимо оно было не верно?

Если Вы имеете в виду кандидатов от Wolfram, то, например, для числа $k=265$ можно доказать (только что проверил своим способом), что сравнение разрешимо по любому модулю. Так что можно, действительно, с каждым кандидатом поработать индивидуально (если я правильно понял maxal).

[dmd]

Да, действительно!

(тогда так)

nno2()=
{
 for(k=1, 1000,

  if(!issquare(k),

   if(k%2, d= k^2-4; f= 4*k, d= (k/2)^2-1; f= k);

   if(kronecker(f, d)==1,

    N= bnfisnorm(bnfinit('X^2 - d), f);

    if(N[2]==1,

     n= lift(N[1]);

     b= polcoeff(n, 1); q= polcoeff(n, 0);
 
     if(k%2, a= (q + b*k)/2, a= q + b*k/2);

     S= factorint(denominator(a));

     for(l=1, #S~,

      m= S[l,1]; s= 0;

      for(i=0, m-1, for(j=0, m-1,

       r= (i^2 + j^2 - k*(i*j + 1)) % m;

       if(!r, s= 1; break(2))

      ));

      if(!s, break())

     );

     if(s, print1(k,", "))
\\     if(s, print(k,"    ",n,"    ",b,"    ",a,"\n"))

    )
   )
  )
 )
};

ответ:

? nno2()
160, 241, 265, 436, 580, 601, 720, 745, 801, 820, 865, 916, 976,

265, 436, 820 вернулись

[nnosipov]

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

160, 241, 265, 436, 580, 601, 720, 745, 801, 820, 865, 916, 976

Вот это и будем теперь проверять.

[maxal]

dmd, похоже, что все ok. У меня только пара замечаний по коду. Во-первых, проверка на символ Кронекера и разделение на четные/нечетные $k$ - излишни, то есть, хуже они не сделают, но и лучше - тоже. Во-вторых, если есть цикл типа for(k=1,1000, if( A, <большой кусок кода> )), то для пущей читабельности и меньшей вложенности лучшпе писать for(k=1,1000, if(!A,next); <большой кусок кода> ).