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

[nnosipov]

Если значение дроби $$\frac{a^2+b^2}{ab+1}$ (где $a$ и $b$ --- натуральные числа) оказалось целым числом, то, как хорошо известно, это число должно быть точным квадратом. Это можно интерпретировать так: уравнение $a^2+b^2=k(ab+1)$ не имеет решений $(a,b)$ в целых числах при любом натуральном $k$, не являющемся точным квадратом. Доказательство проводится методом бесконечного спуска (см., например, https://en.wikipedia.org/wiki/Vieta_jumping). Вместе с тем, при некоторых $k$ отсутствие целочисленных решений можно пытаться доказать гораздо более простым "методом остатков" --- просто доказывая, что соответствующее сравнение

$$a^2+b^2 \equiv k(ab+1) \pmod{m}$$

по некоторому "волшебному" модулю $m$ неразрешимо. Например, для $k=19$ можно взять $m=7$, и доказательство состоится.

А теперь, собственно, вопрос: при каком наименьшем натуральном $k$, не являющемся точным квадратом, этот метод доказательства не сработает (т.е. "волшебный модуль" $m$ подобрать не удастся)?

[waxtep]

Кажется, при $k=3\cdot5\cdot7=105$; по крайней мере, каждое из уравнений $x^2\equiv2\pmod{103}$ и $x^2\equiv-2\pmod{107}$ имеет натуральные решения, и трюк с приведением левой части к полному квадрату не работает; для меньших нечетных чисел одно из уравнений (или оба) не имеют решений в натуральных числах (слава вольфрам-математике! )

[nnosipov]

waxtep в сообщении #1390133 писал(а):

Кажется, при $k=3\cdot5\cdot7=105$

Нет, с этим $k$ все в порядке: можно взять $m=9$, сравнение $a^2+b^2 \equiv 105(ab+1) \pmod{9}$ не имеет решений.

[Shadow]

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

А теперь, собственно, вопрос: при каком наименьшем натуральном $k$, не являющемся точным квадратом, этот метод доказательства не сработает (т.е. "волшебный модуль" $m$ подобрать не удастся)?

При $k=5$ метод остатков точно не сработает, потому что уравнение имеет решений в целых числах. (но не и в натуральных).
UPD
Ай, глупость написаl, извините - при $k=-5$...не годится.

[nnosipov]

Shadow
А действительно, что с отрицательными значениями $k \neq -5$, про которые я почему-то забыл? Здесь, по-видимому, первый раз метод остатков не сработает при $k=-29$ (компьютер не смог найти волшебный модуль за разумное время). Теперь можно пробовать это доказать.

[dmd]

$k=160$

[nnosipov]

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

$k=160$

Да, у меня так же. Но надо бы еще доказать, что сравнение $a^2+b^2 \equiv 160(ab+1) \pmod{m}$ разрешимо при любом натуральном $m$. С одной стороны, здесь работают стандартные рассуждения, с другой --- есть более короткий нестандартный путь.

[dmd]

Вероятно выстроится последовательность 160,241,265,436,580,601,720,.... Как доказать - пока никаких идей.

[nnosipov]

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

Вероятно выстроится последовательность 160,241,265,436,580,.... Как доказать - пока никаких идей.

У меня есть идея. Вот как раз и проверим на этой последовательности, может ли из этой идеи вырасти метод. (Кстати, в OEIS этой последовательности нет.)

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

[nnosipov]

Идея оказалась шаманством и до метода не дотягивает (не работает при $k=241$, хотя для остальных значений из последовательности $160,241,265,436,580$ все хорошо), поэтому привожу решение исходной задачи.

Во-первых, при $k<160$ "волшебный модуль" $m \in \{3,4,5,7,9,11,13,19,23,29,31,37,43,47,53,101,149\}$.

Во-вторых, сравнение

$$ a^2+b^2 \equiv 160(ab+1) \pmod{m} $$

разрешимо при любом натуральном $m$. Поскольку можно положить

$$ a=80b \pm \sqrt{6399b^2+160}, $$

достаточно убедиться, что сравнение

$$ 6399b^2+160-c^2 \equiv 0 \pmod{m} $$

разрешимо при любом $m$. Действительно, при $c=b-48$ оно принимает вид

$$ 2(7b-4)(457b+268) \equiv 0 \pmod{m}. $$

Если $m$ --- степень простого числа, то последнее сравнение разрешимо (из-за линейных сомножителей). Осталось сослаться на китайскую теорему об остатках.

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

[dmd]

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

Действительно, при $c=b-48$ оно принимает вид

а откуда $c=b-48$?

[nnosipov]

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

а откуда $c=b-48$?

Я же говорю, шаманство :) На самом деле, после подстановки $c=b-x$ пытаемся подобрать $x$ так, чтобы квадратный трехчлен относительно $b$ разложился на линейные множители с целыми коэффициентами. Для этого его дискриминант должен быть точным квадратом. Это приводит к уравнению Пелля, которое (вот тут нам просто везет) имеет решения (а $x=48$ --- часть одного из них).

А вот в случае $k=241$, увы, не свезло. В общем, это не алгоритм.

[maxal]

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

Это приводит к уравнению Пелля

Если уж сводить к уравнению Пелля, точнее к уравнению Пелля-Ферма, то это можно сделать сразу и с исходным уравнением. А именно, $a^2+b^2=160(ab+1)$ равносильно $(a-80b)^2 - 6399b^2 = 160$. Найдем его решение:

? bnfisnorm(bnfinit(x^2-6399),160)
%1 = [Mod(-1331788/15*x + 35511572/5, x^2 - 6399), 1]

Т.е. $a-80b = 35511572/5$ и $b=-1331788/15$, и значит $a=-8324/15$. Таким образом, имеем решение по модулю степени любого простого, кроме 3 и 5, и остается рассмотреть только степени последних.

[nnosipov]

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

[dmd]

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

nno2()=
{
 for(k=3, 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)); s= 1;

     for(i=1, #S~,

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

     );

     if(s, print1(k,", "))

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

    )
   )
  )
 )
};

Вывод программы:

? \r nno2.gp
? nno2()
160, 241, 580, 601, 720, 745, 801, 865, 916,

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