Разрешимо ли в целых числах?

[nnosipov]

rightways в сообщении #1457551 писал(а):

Если уравнение $x^2-(z^2+1)y^2=-z^2-14$ неразрешимо в целых числах , то уравнение $x^2-(z^2+1)y^2=z^2+14$ также неразрешимо.
Допустим $x^2-(z^2+1)y^2=z^2+14$ разрешимо для некоторых натуральных $x,y,z$. Так как $x>yz$ то пусть $x=yz+y_1$ и $x_1=y_1z-y$. Тогда

$$(yz+y_1)^2+(y_1z-y)^2=x^2_1+x^2$$

Последнее эквивалентна равенству $(z^2+1)y^2-x^2=x^2_1-(z^2+1)y_1^2$
Но $(z^2+1)y^2-x^2=-z^2-14$. Противоречие.

Да, только я об этом выше уже писал. Ну да ладно, это мелкий момент.

[Iam]

rightways в сообщении #1457551 писал(а):

Если уравнение $x^2-(z^2+1)y^2=-z^2-14$ неразрешимо в целых числах , то уравнение $x^2-(z^2+1)y^2=z^2+14$ также неразрешимо.

Уравнение $x^2-(z^2+1)y^2=z^2+2222$ (также как и $x^2-(z^2+1)y^2=z^2+14$) неразрешимо как сравнение по модулю 8.

[nnosipov]

Iam в сообщении #1457770 писал(а):

Уравнение $x^2-(z^2+1)y^2=z^2+2222$ (также как и $x^2-(z^2+1)y^2=z^2+14$) неразрешимо как сравнение по модулю 8.

А если взять $x=y=z=1$? Скорее наоборот, оба этих сравнения разрешимы по любому модулю.

[Iam]

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

А если взять $x=y=z=1$? Скорее наоборот, оба этих сравнения разрешимы по любому модулю.

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

[nnosipov]

Например, можно попробовать доказать, что сравнение $x^2-(15^2+1)y^2+15^2+14 \equiv 0 \pmod{m}$ разрешимо при любом $m$. Это похоже на правду (компьютер не смог подыскать $m$ за несколько минут).

[rightways]

Походу эту задачу никто не решит

[12d3]

Будем решать уравнение $x^2=y^2z^2+y^2+z^2+2222$. Считаем все переменные неотрицательными.
Если $(x,y,z)$ - решение, то $(|x-2z(y-xz+yz^2)|,|y-2z(x-yz)|,z)$ - тоже решение. Организуем спуск таким образом, чтобы минимизировать $\max (y,z)$. Спуск закончится либо когда одна из переменных станет нулем (а поскольку 2222 дает остаток 2 при делении на 4, то этого быть не может), либо когда станет $y \le z(x-yz)$ и $z \le y(x-yz)$.
Сделаем замену $x=yz+t$, тогда уравнение преобразуется к виду $2222-t^2=2tyz-y^2-z^2 = y(zt-y)+z(yt-z)$, и условия окончания спуска будут такие: $zt-y \ge 0$ и $yt-z \ge 0$, а значит $y(zt-y)+z(yt-z) \ge 0$. Получаем, что в конце спуска при придем к решению, у которого $t^2 \le 2222$.
Теперь докажем, что ни при каком положительном $t \le 47$ решений не будет.
Пусть $t \equiv \pm 1 \pmod p$, где $p$ - какое угодно натуральное число. Тогда $2222-1 \equiv \pm 2yz -y^2-z^2 \equiv -(y \pm z)^2 \pmod p$. Отсюда вывод: если -2221 не является квадратичным вычетом по модулю $p$, то $t$ не может принимать значения $kp \pm 1$.
А поскольку -2221 является квадратичным невычетом по модулям 3,4,7,13,17,23,29,41, то это отсекает вообще все значения $t$ от 1 до 47. Так что уравнение неразрешимо.

[nnosipov]

12d3
Спасибо, это похоже на правду. А откуда взялись формулы спуска?

-- Вс апр 26, 2020 12:10:09 --

12d3 в сообщении #1457959 писал(а):

Спуск закончится либо когда одна из переменных станет нулем (а поскольку 2222 дает остаток 2 при делении на 4, то этого быть не может), либо когда станет $y \le z(x-yz)$ и $z \le y(x-yz)$.

Вот здесь бы поподробнее. Мне кажется, это ключевое место, остальное уже технические детали.

[12d3]

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

А откуда взялись формулы спуска?

Есть у нас есть решение уравнения $x^2-(z^2+1)y^2=z^2+2222 \Leftrightarrow (x+y\sqrt{z^2+1})(x-y\sqrt{z^2+1}) = z^2+2222$.
Шаг первый. Умножаем левую и правую часть на $(z+\sqrt{z^2+1})(z-\sqrt{z^2+1})=-1$, получаем решение уравнения $x^2-(z^2+1)y^2=-z^2-2222 \Leftrightarrow x^2-(y^2-1)z^2=y^2-2222$.
Шаг второй. Умножаем левую и правую часть на $(y-\sqrt{y^2-1})(y+\sqrt{y^2+1})=1$, получаем новое решение уравнения $x^2-(y^2-1)z^2=y^2-2222 \Leftrightarrow x^2-(z^2+1)y^2=-z^2-2222$.
Шаг третий. Умножаем левую и правую часть на $(z+\sqrt{z^2+1})(z-\sqrt{z^2+1})=-1$, получаем новое решение уравнения $x^2-(z^2+1)y^2=z^2+2222$.
Если выразить $x,y,z$, получившиеся на третьем шаге через те $x,y,z$, которые были до первого шага, получатся формулы спуска для уравнения $x^2-(z^2+1)y^2=z^2+2222$. Так как это уравнение симметрично относительно $y$ и $z$, можно спускаться по $z$, потом по $y$, потом по $z$, и т.д., пока не упремся.

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

Вот здесь бы поподробнее. Мне кажется, это ключевое место, остальное уже технические детали.

У нас по формулам спуска $y_1 = |y-2z(x-yz) |$. Спуск дальше по $y$ возможен, если $y_1 < y \Leftrightarrow \begin{cases}y-2z(x-yz) < y \\ y-2z(x-yz) > -y \end{cases} \Leftrightarrow \begin{cases}z > 0 \\ y > z(x-yz) \end{cases}$. Аналогично для спуска по $z$.

[nnosipov]

12d3
OK, спасибо. Как, кстати, задача? Поделитесь ощущениями. (Любителей такого жанра задач здесь немного, поэтому интересно мнение каждого.)

Мне вот этот момент понравился:

12d3 в сообщении #1457959 писал(а):

А поскольку -2221 является квадратичным невычетом по модулям 3,4,7,13,17,23,29,41, то это отсекает вообще все значения $t$ от 1 до 47.

У меня в аналогичном месте просто незатейливый перебор конечного числа вариантов.

[Iam]

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

...интересно мнение каждого

Конечно, задача понравилась. К сожалению, я обратил на нее внимание ночью незадолго до решения 12d3 и надеялся, что она полежит еще какое-то время, чтобы в удовольствие поразмыслить в свободные минутки. Подсказка, пожалуй, излишняя – сужает творческий поиск. А сейчас на языке "я тоже так хотел" . В принципе спуск – это один из напрашивающихся здесь вариантов, делал некоторые безуспешные попытки. Конечно, я бы тоже проверил перебором до 47. В памяти задачка осталась и в фоновом режиме еще какие-нибудь идеи будет генерировать. К сожалению, время лимитировано.

[rightways]

Да, задача супер. А авторское решение есть?)

[nnosipov]

rightways в сообщении #1458123 писал(а):

А авторское решение есть?)

Есть, конечно. Вчера отправил эту задачу в Amer. Math. Monthly. Если им не понравится (судя по прошлому опыту, происходит с вероятностью 1/2), выложу здесь со всеми подробностями и комментариями. Могу сказать, что предыдущую задачу на эту тему (см. topic136100.html) они опубликовали.

[nnosipov]

12d3 в сообщении #1457959 писал(а):

Теперь докажем, что ни при каком положительном $t \le 47$ решений не будет.
Пусть $t \equiv \pm 1 \pmod p$, где $p$ - какое угодно натуральное число. Тогда $2222-1 \equiv \pm 2yz -y^2-z^2 \equiv -(y \pm z)^2 \pmod p$. Отсюда вывод: если -2221 не является квадратичным вычетом по модулю $p$, то $t$ не может принимать значения $kp \pm 1$.
А поскольку -2221 является квадратичным невычетом по модулям 3,4,7,13,17,23,29,41, то это отсекает вообще все значения $t$ от 1 до 47. Так что уравнение неразрешимо.

Можно ли это рассуждение превратить в алгоритм?

Пусть мы решаем такую задачу: для натуральных $k \equiv 6 \pmod{8}$ найти достаточное условие того, что для любых натуральных чисел $y$, $z$ число $y^2z^2+y^2+z^2+k$ не будет точным квадратом. Из решения 12d3 следует, что таким условием может быть следующее: для любой пары $(y,z)$ натуральных чисел, удовлетворяющей неравенствам $y \leqslant z<\sqrt{y^2+k}$, число $y^2z^2+y^2+z^2+k$ не является точным квадратом. Количество таких пар $(y,z)$ есть величина порядка $k\ln{k}$. Таким образом, достаточно провести порядка $k\ln{k}$ "тестов на квадратность". Предлагается дать другое условие на $k$, для проверки которого потребовалось бы существенно меньшее (по порядку) количество "тестов на квадратность".

[nnosipov]

И аналогичная задача про выражение $y^2z^2+y^2+z^2-k$, где $k \equiv 2 \pmod{8}$ --- натуральное число. Например, при $k=6666$ указанное выражение не может давать точный квадрат ни при каких натуральных $y$, $z$.