Имеет ли уравнение целочисленное решение?

[flacs]

Уважаемые форумчане, помогите мне решить вот такой вопрос:

UPD: Поправил стартовый топик.

Требуется выяснить разрешимость решения уравнения, при условии целочисленного решения в целых неотрицательных числах

$(9x+r_1)(9y+r_2)=N$, где $N$ - целое число, $r_1,r_2$ - остатки от 2х множителей, которые в результате составляют число $N$.
И $r_1,r_2$ - числа по модулю 9.

Пример:

$(9x+1)(9y+1)=703$ - решение есть ( посмотреть)
$(9x+2)(9y+5)=703$ - решений нет ( посмотреть)
$(9x+8)(9y+8)=703$ - решение есть в отрицательных числах ( посмотреть)

Можно ли быстрым способом установить разрешимость решения уравнения при заданных остатках $r_1,r_2$, как это происходит при решении к примеру при решении диофантового уравнения, или уравнения по модулю.

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Sonic86]

Вопрос непонятен. Начните с четкой формулировки.

flacs в сообщении #1024375 писал(а):

нумерическая сумма

Что это?

flacs в сообщении #1024375 писал(а):

все числа исходного числа

Что такое "чИсла числА"?

flacs в сообщении #1024375 писал(а):

подобрать пару остатков двух множителей?

О каких множителях идет речь?

[ИСН]

Число 7481 - простое; оно не разлагается на множители вообще никак, кроме $1\cdot7481$.
В ближайшее время все, кто свободен от других задач, будут гадать, чего же Вам было нужно на самом деле.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

Вот и поговорили. Продолжаем приводить тему в порядок.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

Стартовый пост отредактирован.

[Lia]

flacs
А свое условие $N\equiv 1\pmod 9$ Вы сняли? Это непринципиально, просто уточнение постановки задачи.

[nnosipov]

flacs в сообщении #1024375 писал(а):

Можно ли быстрым способом

Что такое "быстрым способом"? Как Вы определяете, что один способ быстрый, а другой --- не очень?

[svv]

flacs в сообщении #1024375 писал(а):

Требуется выяснить разрешимость решения уравнения, при условии целочисленного решения в целых неотрицательных числах.

Итого:
Выяснить разрешимость уравнения в целых неотрицательных числах.

[Sonic86]

Напишу задачу, как понял я: дано $N,r,s, 0\leqslant r,s < 9$ и уравнение $(9x+r)(9y+s)=N$, надо найти $x,y$.
Ответ: сводится к факторизации $N$, никаких специальных улучшений имеющаяся информация не дает (просто потому, что остатки от деления принимают всего $O(1)$ пар значений и находятся за $O(\ln N)$ времени)

[flacs]

Lia в сообщении #1025185 писал(а):

flacs
А свое условие $N\equiv 1\pmod 9$ Вы сняли? Это непринципиально, просто уточнение постановки задачи.

Снял, ибо при любом x,y в левой части уравнения будет в итоге сравнение $1\equiv 1\pmod 9$, значения $x,y=0$, исключаю как тривиальный случай, т.к. при умножении, и при сложении по модулю 9, получается снова 9 ($m\equiv 9\pmod 0$)

-- 09.06.2015, 20:56 --

Sonic86 в сообщении #1025356 писал(а):

Напишу задачу, как понял я: дано $N,r,s, 0\leqslant r,s < 9$ и уравнение $(9x+r)(9y+s)=N$, надо найти $x,y$.
Ответ: сводится к факторизации $N$, никаких специальных улучшений имеющаяся информация не дает (просто потому, что остатки от деления принимают всего $O(1)$ пар значений и находятся за $O(\ln N)$ времени)

Вы неверно поняли условие, мне не нужно находить x,y - (эти значение вероятно можно найти только перебором $x,y$), мне нужно проверить уравнение на разрешимость целочисленого решения в неотрицательных числах. Подобно тому - как это происходит в Диофантовых уравнениях (где находится наибольший общий делитель), либо в уравнениях по модулю, где производится ряд математических действий, и сразу дается ответ. Еще пример квадратичный вычет по модулю простого числа (символ Лежандра - тоже очень быстрое вычисление), все эти примеры доказывают что Бинарный ответ (разрешимости), дается не после перебора всех значений, а после специальных сравнений.

[Sonic86]

flacs в сообщении #1025360 писал(а):

мне нужно проверить уравнение на разрешимость целочисленого решения в неотрицательных числах.

Это бессмысленная фраза. Пишите условие задачи вменяемо.

-- Вт июн 09, 2015 17:05:25 --

Либо еще вариант: Вы изобретаете сравнения по модулю с квадратными колесами и спрашиваете, всегда ли разрешимо сравнение $rs\equiv N\pmod 9$ для $3\nmid N$. Ответ: да, всегда ($6=\varphi(9)$ решений)

[flacs]

Sonic86 в сообщении #1025369 писал(а):

Либо еще вариант: Вы изобретаете сравнения по модулю с квадратными колесами и спрашиваете, всегда ли разрешимо сравнение $rs\equiv N\pmod 9$ для $3\nmid N$. Ответ: да, всегда ($6=\varphi(9)$ решений)

Я новичок поэтому и спрашиваю такое сравнение разрешимости вообще реально? либо нужна дополнительная информация для сравнения?
Ведь Wolfram Alpha выдает целочисленных решений нет, в случае $(9x+2)(9y+5)=703$.

-- 09.06.2015, 21:13 --

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

flacs в сообщении #1024375 писал(а):

Можно ли быстрым способом

Что такое "быстрым способом"? Как Вы определяете, что один способ быстрый, а другой --- не очень?

Метод нахождения наибольшего общего делителя считается быстрым (принадлежит к классу P), перебор значений (экспоненциальная задача)

-- 09.06.2015, 21:19 --

Если я подберу сравнения не по модулю 9, а к примеру по модулю простого числа, ситуация изменится?

[Sonic86]

flacs в сообщении #1025374 писал(а):

Я новичок поэтому и спрашиваю такое сравнение разрешимости вообще реально? либо нужна дополнительная информация для сравнения?
Ведь Wolfram Alpha выдает целочисленных решений нет, в случае $(9x+2)(9y+5)=703$.

Ладно, еще вариант. Задача звучит так: дано $N,r,s, 0\leqslant r,s < 9$ и уравнение $(9x+r)(9y+s)=N$, надо быстро (пусть за полиномиальное время) определить, разрешимо ли это уравнение.
Ответ: берем по модулю $9$. Если $rs\not\equiv N\pmod 9$, то уравнение неразрешимо. Иначе придется факторизовать $N$ патамушта

Sonic86 в сообщении #1025356 писал(а):

никаких специальных улучшений имеющаяся информация не дает (просто потому, что остатки от деления принимают всего $O(1)$ пар значений и находятся за $O(\ln N)$ времени)

flacs в сообщении #1025374 писал(а):

Если я подберу сравнения не по модулю 9, а к примеру по модулю простого числа, ситуация изменится?

Думаю, что нет по тем же причинам.