Диофантово уравнение 2-го порядка

[Gagarin1968]

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

Фактически это рассуждение по модулю 9.

Ну да, но это получается автоматически в процессе решения.
Вот к примеру случай $x \equiv 1\pmod{3} и y \equiv 1\pmod{3}$:

Положим $x=3m+1$, $y=3n+1$

Тогда $x^2+4xy+y^2=(3m+1)^2+4(3m+1)(3n+1)+(3n+1)^2=9(m^2+n^2+4mn+2m+2n)+6$,

в то время как $111\equiv 3\pmod{9}$
Но в любом случае полный перебор очень быстро приводит к решению.

[nnosipov]

Gagarin1968 в сообщении #1536096 писал(а):

Ну да, но это получается автоматически в процессе решения.

Тем не менее, это лишний логический ход.

Gagarin1968 в сообщении #1536096 писал(а):

Но в любом случае полный перебор очень быстро приводит к решению.

В данном случае да, но это просто повезло с выражением. А вот будет что-нибудь типа уравнения $x^4=y^3+111$. Здесь придется уже думать, как сократить перебор, ибо "волшебный модуль" в данном случае не слишком маленький.

[Gepidium]

Спасибо, друзья, вы накидали столько идей, что я уже давно решила эту задачу. Я правильно понимаю, что исходное уравнение неразрешимо?
И ещё успела почитать учебник.

-- 23.10.2021, 19:55 --

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

Между тем, можно найти такой модуль $m<9$, что сравнение $x^2+4xy+y^2 \equiv 111 \pmod{m}$ будет неразрешимым.

nnosipov, маленький вопрос: Вы предлагаете найти такой модуль, уже априори зная, что сравнение должно быть неразрешимо.
А как Вы это можете заранее знать?

[nnosipov]

Gepidium в сообщении #1536102 писал(а):

Я правильно понимаю, что исходное уравнение неразрешимо?

Да, правильно.

Gepidium в сообщении #1536102 писал(а):

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

Нет, не так: я предлагаю искать "волшебный модуль" (по которому сравнение неразрешимо), надеясь, что он есть. Дело в том, что бывают такие неразрешимые уравнения, для которых нет никакого "волшебного модуля" (например, таково уравнение $x^2-34y^2=-1$). Так что никаких "должно быть неразрешимо" быть не может. Мы можем только скромно надеяться, что "волшебный модуль" найдется и, тем самым, обеспечит нам относительно легкий способ решить задачу. В противном случае придется кричать караул изучать более сложные методы решения (в частности, доказательства неразрешимости) диофантовых уравнений.

[Gepidium]

nnosipov
Это я всё понимаю.
Но Ваша первая реакция на мою задачу была

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

Докажите, что решений нет, рассмотрев это уравнение по подходящему модулю

Получается, что Вы всё-таки априори уже знали о неразрешимости уравнения. По его виду?Объясните, пожалуйста, как? Или у Вас сверхинтуиция?

[nnosipov]

Gepidium в сообщении #1536126 писал(а):

Получается, что Вы всё-таки априори уже знали о неразрешимости уравнения.

Что значит априори? Я на него посмотрел и понял, в чем здесь дело. В левой части --- квадратичная форма с положительным дискриминантом, не являющемся точным квадратом, а справа --- ненулевое целое число. В общем случае такие уравнения решаются с помощью теории уравнений Пелля. Ответом будет либо бесконечное множество решений, либо пустое множество. В частности, не бывает так, что множество решений конечно, но не пусто. Чтобы найти бесконечное множество решений, нужно знать теорию уравнений Пелля. Но, судя по тем методам, что Вы пробовали применить для решения уравнения, о теории уравнений Пелля говорить пока рано. Тем не менее, задача должна как-то элементарно решаться (без теории уравнений Пелля). Как? Учитывая тип уравнения, годится только метод остатков, именно он позволит элементарно доказать, что решений нет. Значит, нужно искать "волшебный модуль". И поиски, как Вы понимаете, были недолгими.

[Gepidium]

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

В общем случае такие уравнения решаются с помощью теории уравнений Пелля. Ответом будет либо бесконечное множество решений, либо пустое множество. В частности, не бывает так, что множество решений конечно, но не пусто.

nnosipov
Простите меня, но возможно я не успеваю за Вашим полетом мысли.
В этой же самостоятельной работе было такое уравнение: $10x^2+11xy+3y^2=7$.
В левой части квадратичная форма с положительным дискриминатом, справа - ненулевое число, в общем всё как вы описали.
Методов решения уравнений Пелля я не знаю. Но это уравнение я решила, разложив левую часть на множители. Получилось вполне себе конечное множество решений - 4 пары чисел.
Просветите меня, в чем противоречие с Вашими словами?

[nnosipov]

Gepidium в сообщении #1536154 писал(а):

В левой части квадратичная форма с положительным дискриминатом, справа - ненулевое число, в общем всё как вы описали.

Нет, не всё. Читайте мой текст внимательней.

[zykov]

$D=11^2-4\cdot 10\cdot 3=121-120=1=1^2$

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

квадратичная форма с положительным дискриминантом, не являющемся точным квадратом

[Gepidium]

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

Читайте мой текст внимательней.

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

квадратичная форма с положительным дискриминантом, не являющемся точным квадратом

Да, это я оплошала. Но неужели это обстоятельство так влияет на решение?
Вообще меня очень интересует, как можно, взглянув на уравнение, определить, разрешимо ли оно, и если разрешимо, то конечно или бесконечно множество решений?
Вот те признаки, что Вы упомянули - где можно почитать об этом. В моём учебнике ничего такого нет. Учебник у меня английский. Rosen, Elementary number theory, 2010

[nnosipov]

Gepidium в сообщении #1536160 писал(а):

Вообще меня очень интересует, как можно, взглянув на уравнение, определить, разрешимо ли оно, и если разрешимо, то конечно или бесконечно множество решений?

Да никак нельзя (в общем случае), погуглите теорему Матиясевича. Но есть классы диофантовых уравнений, для которых придумали алгоритмы решения. Этим и живем.

Вот Вам для тренировки уравнение (которое принадлежит семейству уравнений, для которого есть алгоритм решения): $y^2=x^4+x^3+x^2+x+1$. Если сможете его сами решить (а здесь есть элементарное решение), то это будет очень неплохо. В некоторых книжках учебного характера это уравнение решено неверно (рассуждение содержит логические ошибки), так что здесь не все так просто.

Gepidium в сообщении #1536160 писал(а):

Учебник у меня английский. Rosen, Elementary number theory, 2010

Посмотрю, что за книжка. Это случайно не тот Роузен, который вместе с Айэрлендом (Ireland), Классическое введение в современную теорию чисел? Вот, кстати, рекомендую.

Upd. Нет, не тот.

Gepidium в сообщении #1536160 писал(а):

Вот те признаки, что Вы упомянули - где можно почитать об этом.

Долгий разговор. Будет время, напишу.

[Gepidium]

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

Вот Вам для тренировки уравнение (которое принадлежит семейству уравнений, для которого есть алгоритм решения): $y^2=x^4+x^3+x^2+x+1$. Если сможете его сами решить (а здесь есть элементарное решение), то это будет очень неплохо.

nnosipov
Я попробую, самой интересно.
А решить в натуральных или целых?
Только, если Вы не против, я для этой задачи открою отдельную тему, ведь продолжать здесь - это вроде как оффтопик, модераторы будут сердиться.
Или всё же ничего, как считаете?

[nnosipov]

Gepidium в сообщении #1536160 писал(а):

Rosen, Elementary number theory, 2010

Нашел только Kenneth H. Rosen, Elementary number theory and its applications, 1984. Здесь даже есть раздел про уравнения Пелля, но какой-то урезанный. В частности, то уравнение Пелля, которое возникает в задаче (а именно: $x^2-3y^2=111$), решить не удастся, если опираться только на материал этого параграфа.

А в целом учебник для undergraduate level вполне годен: стандартный набор фактов начального уровня с подробными доказательствами, после каждого параграфа есть упражнения в достаточном количестве, даже для выполнения с компьютером (Computer Projects); подробно рассказано о функции Кармайкла, псевдопростых числах Эйлера и строго псевдопростых числах. Однако: практически нет сложных задач (упражнений со звездочкой), да и староват уже учебник (цитата: It has been conjectured that there are infinitely many Carmichael numbers, but so far this has not been demonstrated.) Возможно, в издании 2010 года все это исправлено.

-- Вс окт 24, 2021 14:00:01 --

Gepidium в сообщении #1536163 писал(а):

А решить в натуральных или целых?

Пусть в натуральных, это неважно.

Вообще, здесь на форуме это (и подобные ему) уравнения обсуждались много раз. Но важны самостоятельные попытки. Как что-нибудь придумаете, пишите здесь, в этой теме (если будет что-то содержательное, модераторы потом перенесут этот кусок в одну из уже существующих тем).

[Батороев]

Gepidium в сообщении #1536062 писал(а):

Решить в целых уравнение $x^2+4xy+y^2=111$.

Рассмотрите остатки по модулю $4$.

-- 24 окт 2021 14:35 --

(Оффтоп)

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

Значит, нужно искать "волшебный модуль"

Извиняюсь, сразу не заметил Вашу подсказку.

[Gagarin1968]

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

Gepidium в сообщении #1536070 писал(а):

А как определить, какой модуль подходящий?

Да подряд пробовать и надеяться, что повезет. 2 не подходит, 3 тоже. А 4?

nnosipov
Да, Вы правы, по $\mod 4$ неразрешимость видна ещё быстрее, чем по $\mod 3$.