2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Неразрешимое сравнение
Сообщение08.01.2021, 21:51 
Заслуженный участник


20/12/10
8858
Докажите, что для любого натурального $k$ найдется такое натуральное $m$, что сравнение $$x^2+y^2+k \equiv 0 \pmod{m}$$ не имеет решений.

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 02:15 


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

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 07:13 
Аватара пользователя


23/05/20
336
Беларусь
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;$
По-видимому, я не так понял задачу?? :-(

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 07:53 
Заслуженный участник


20/12/10
8858
lel0lel в сообщении #1499796 писал(а):
Или есть какой-то подвох?
Да нет, никакого подвоха нет. Я забыл написать, что задача простая :-) Она не моя, найдена вот здесь https://www.mat.uniroma2.it/~tauraso/AMM/amm.html (Problem 12200).
StepV в сообщении #1499809 писал(а):
По-видимому, я не так понял задачу??
Да. Вчитайтесь повнимательней в условие. Требуется найти такой модуль $m$, по которому сравнение будет неразрешимым.

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

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 13:27 
Аватара пользователя


23/05/20
336
Беларусь
nnosipov в сообщении #1499812 писал(а):
Требуется найти такой модуль $m$, по которому сравнение будет неразрешимым.


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

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 13:37 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 14:27 
Аватара пользователя


23/05/20
336
Беларусь
nnosipov в сообщении #1499856 писал(а):
можете ли Вы привести пример неразрешимого сравнения с одним (например) неизвестным?


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

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 14:43 
Заслуженный участник


20/12/10
8858
Например, пусть $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}$ окажется неразрешимым.

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

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 16:13 
Аватара пользователя


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


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

 Профиль  
                  
 
 Re: Неразрешимое сравнение
Сообщение09.01.2021, 16:19 
Заслуженный участник


20/12/10
8858
Вот и хорошо :)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group