Неразрешимое сравнение

[nnosipov]

Докажите, что для любого натурального $k$ найдется такое натуральное $m$, что сравнение

$$x^2+y^2+k \equiv 0 \pmod{m}$$

не имеет решений.

[lel0lel]

Для произвольного $k$ существует натуральное $m$, такое что при любом натуральном $n$ число $nm-k$ имеет хотя бы один простой делитель вида $4s+3$ в нечётной степени. Вроде доказывается это довольно просто. Или есть какой-то подвох?

[StepV]

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

не имеет решений

Не понимаю, почему не будет решений? Вроде берем кольцо $Z_m$, где $m=x^2+y^2+k$ и в нем решения уравнения существуют. Например
$ x=1; y=2; k=3;$ в $ Z_8=0;$
$ x=2; y=3; k=3;$ в $Z_8=0;$
$ x=2; y=5; k=3;$ в $Z_8=0;$
По-видимому, я не так понял задачу??

[nnosipov]

lel0lel в сообщении #1499796 писал(а):

Или есть какой-то подвох?

Да нет, никакого подвоха нет. Я забыл написать, что задача простая Она не моя, найдена вот здесь https://www.mat.uniroma2.it/~tauraso/AMM/amm.html (Problem 12200).

StepV в сообщении #1499809 писал(а):

По-видимому, я не так понял задачу??

Да. Вчитайтесь повнимательней в условие. Требуется найти такой модуль $m$, по которому сравнение будет неразрешимым.

Кстати, о разрешимости: для любого целого $k$ указанное сравнение будет разрешимо при любом простом модуле $m$.

[StepV]

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

Требуется найти такой модуль $m$, по которому сравнение будет неразрешимым.

В силу того, что на $m$ не наложено никаких условий и $ x,y,k,m $ - натуральные, то мы при любых $x,y,k$ принимаем $m=x^2+y^2+ k$ и сравнение разрешимо, даже, если слева получается простое число.
Если я ошибаюсь, может подскажите, в какую сторону двигаться?

[nnosipov]

Ну, давайте попробуем. Вы понимаете, что такое сравнение по модулю с неизвестным (неизвестными)? Если да, то представляете ли Вы, что значит "решить сравнение с неизвестным (неизвестными)"? Если опять да, то понимаете ли Вы, что бывают неразрешимые сравнения (т.е. не имеющие ни одного решения)? И если снова да, то можете ли Вы привести пример неразрешимого сравнения с одним (например) неизвестным?

[StepV]

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

можете ли Вы привести пример неразрешимого сравнения с одним (например) неизвестным?

Посмотрел в Интернете про сравнения с неизвестным. Это "теория чисел", которую я не изучал и , по-видимому в будущем она мне не понадобится. Поэтому в эту тему дальше углубляться не буду. Спасибо вам за проявленное внимание.
Только одна просьба! Можете привести хотя бы один набор чисел решения, для примера? Хотелось бы убедиться своими глазами в существовании невозможного??

[nnosipov]

Например, пусть $k=5$. Тогда можно взять $m=4$, так как сравнение

$$x^2+y^2+5 \equiv 0 \pmod{4}$$

не имеет решений (т.е. ни при каких целых числах $x$ и $y$ число $x^2+y^2+5$ не будет кратно $4$). Это можно проверить непосредственным перебором всех пар остатков от деления $x$ и $y$ на $4$.

Для $k=7$ годится $m=49$: сравнение

$$x^2+y^2+7 \equiv 0 \pmod{49}$$

также неразрешимо. И это утверждение можно проверить перебором возможных остатков (теперь уже от деления на $49$), однако есть и более короткий способ (но вот здесь уже нужно кое-что знать из элементарной теории чисел).

Суть задачи в том, чтобы для каждого натурального значения $k$ предъявить (или доказать, что существует) такой модуль $m$, по которому сравнение $x^2+y^2+k \equiv 0 \pmod{m}$ окажется неразрешимым.

Ну как, понятно?

[StepV]

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

Суть задачи в том, чтобы для каждого натурального значения $k$ предъявить (или доказать, что существует) такой модуль $m$, по которому сравнение $x^2+y^2+k \equiv 0 \pmod{m}$ окажется неразрешимым.
Ну как, понятно?

Вроде именно об этом вы написали в посту https://dxdy.ru/post1499812.html#p1499812, а вопрос стал ясен, когда посмотрел на решение. Спасибо, понятно и очень классно!!

[nnosipov]

Вот и хорошо :)