Диофантовы уравнения.Метод остатков.

[Stensen]

Доброго всем времени суток. Уважаемые помогите разобраться. Доказать, что не разрешимо в целых числах:
$7x^2=5y^2+3$. В указании к решению сказано, что нужно проверить остатки от деления левой и правой частей на $3$. Остатки совпадают при $x=3k,\, y=3n$. Далее из приложенного в задачнике решения понятно. Но почему проверять остатки от деления нужно именно на $3$, а не на другое число?
Аналогичные рекомендации в задачнике для решения:

(1). $x^2-3y^2=8$, по модулю $3$,

(2). $15x^2-7y^2=9$, по модулю $5$,

(3). $2x^2-5y^2=7$, по модулю $4$.

Мне понятно только для (1). Если так: $x^2-8=3y^2$, то на $3$ должна делиться левая часть и нужно проверять остатки от деления её на $3$.
А на чем основан выбор таких модулей для остальных уравнений?

[Sinoid]

Stensen в сообщении #1193631 писал(а):

Но почему проверять остатки от деления нужно именно на $3$, а не на другое число?

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

[Sonic86]

Stensen в сообщении #1193631 писал(а):

Но почему проверять остатки от деления нужно именно на $3$, а не на другое число?

В общем случае трудно сказать, ибо 10-я проблема Гильберта.
Можно привести чуть более понятное общее соображение: пусть надо решить диофантово уравнение $F=0$ - в $\mathbb{Z}$. А давайте порешаем его в $\mathbb{Z}_m$. Если есть хотя бы одно $m$ такое, что $F \neq 0$ для всех значений переменных в $\mathbb{Z}_m$, то исходное уравнение $F=0$ решений не имеет тоже. А если мы такого $m$ не нашли или если его даже не существует, то фиг знает. (т.е. есть принцип Хассе работает не для всех уравнений). А если уравнение имеет хотя бы одно, пусть даже тривиальное целое или рациональное решение, то эта идея не сработает априори - решения всегда будут во всех $\mathbb{Z}_m$.

Далее, мы можем просто перебирать все $m=1;2;3;...$. Иногда перебор можно оптимизировать. Например, можно не рассматривать $m=1$. Конкретно для нашего уравнения мы видим, что если взять в качестве $m$ делитель одного из коэффициентов кроме свободного члена, то одна из переменных исчезает и шансы иметь решение у уравнения уменьшаются. Здесь это работает, но в общем случае может не сработать.

Можно было бы спросить - почему именно $\mathbb{Z}_m$? Ответ: потому что $\mathbb{Z}_m$ - это всевозможные ядра эпиморфизмов $\mathbb{Z}$, других (к сожалению или к счастью) нету.

Обоснование для модуля $4$ будет чуть посложнее - тоже можно догадаться. Но в любом случае это все не особо алгоритмично - люди ищут удачные варианты.

[Stensen]

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

Stensen в сообщении #1193631 писал(а):

Но почему проверять остатки от деления нужно именно на $3$, а не на другое число?

В общем случае трудно сказать, ибо 10-я проблема Гильберта.
Можно привести чуть более понятное общее соображение: пусть надо решить диофантово уравнение $F=0$ - в $\mathbb{Z}$. А давайте порешаем его в $\mathbb{Z}_m$. Если есть хотя бы одно $m$ такое, что $F \neq 0$ для всех значений переменных в $\mathbb{Z}_m$, то исходное уравнение $F=0$ решений не имеет тоже.

Подумал, что 10-ю Гильберта пока не буду решать. Пока возникли попутные вопросы, проясните пожалуйста:
1) изложенное Вами общее соображение решения (доказательства отсутствия решений) диофантова уравнения $F=0$ в $\mathbb{Z}_m$, так понимаю, применимо и для решения уравнений более высоких степеней и показательных типа:
$x^3+21y^2+5=0$

$2^x-3^y=1$

или для них применяются другие методы?

2) подскажите по решению следующего, все ли верно? Доказать, что нет решений для: $2x^2=5y^2+7$, (по рекомендации автора по модулю $4$):

ищу остатки от деления на $4$ обеих частей уравнения и обнаруживаю, что остатки совпадают: $2x^2 \equiv 5y^2+7 \equiv 0 \,(\bmod 4) $ при $x_1=4k, \, x_2=4k+2, \, y_1=4m+1, \, y_2=4m+3$. Если правильно понимаю, нужно перебрать все эти варианты: $(x_1,y_1),\, (x_2,y_1),\, (x_1,y_2),\, (x_2,y_2) ,\,$ и посмотреть что получится? Решаю для: $x_1=4k, \, y_1=4m+1$, подставляю в $2x^2=5y^2+7$ и получаю:
$8k^2=10m(2m+1) +3$, из чего видно, что слева и справа стоят числа разной четности: слева четное, а справа нечетное, из чего заключаю, что решений при таких $x,\, y$ нет. Для других вариантов $x,\, y$ аналогичная ситуация. Т.е. решений в целых это уравнение не имеет. Правильно ли я рассуждаю?

[Sonic86]

Stensen в сообщении #1193739 писал(а):

изложенное Вами общее соображение решения (доказательства отсутствия решений) диофантова уравнения $F=0$ в $\mathbb{Z}_m$, так понимаю, применимо и для решения уравнений более высоких степеней и показательных типа:
$x^3+21y^2+5=0$

$2^x-3^y=1$

или для них применяются другие методы?

Да, применимо. Но и другие методы тоже применяются конечно

Stensen в сообщении #1193739 писал(а):

2) подскажите по решению следующего, все ли верно?

Да, верно, только немного неоптимально:
1) Раз уж Вы употребляете отношение сравнимости по модулю $\equiv$, то Вам не нужно писать вещи типа $x_2=4k+2$, можно писать $x_2\equiv 2\pmod 4$ (или даже $x_2\equiv 2(4)$ - так не нужно выбирать новую букву для обозначения, которая все равно практически не будет никак использована)
2) $2$ делит $4$, потому можно было сначала взять уравнение по модулю $2$, в результате мы бы сразу получили, что $y$ нечетно без перебора 4-х более сложных вариантов. Далее полезно помнить, что если $y\equiv 1 (2)$, то $y^2\equiv 1 (8)$, и далее взяв по модулю $8$ уже получим, что решений нет. Модуль у меня $8$, а не $4$, потому что сокращать на $2$ приходится.

[iou]

Stensen в сообщении #1193739 писал(а):

2) подскажите по решению следующего, все ли верно? Доказать, что нет решений для: $2x^2=5y^2+7$, (по рекомендации автора по модулю $4$):

В этом примере (на мой взгляд) проще даже смотреть на уравнение по модулю $7$, поделить всё на $5$ и сказать, что $6 - $ квадратичный невычет по модулю 7.

[Stensen]

Спасибо всем, буду впитывать

[Sonic86]

iou в сообщении #1193757 писал(а):

В этом примере (на мой взгляд) проще даже смотреть на уравнение по модулю $7$, поделить всё на $5$ и сказать, что $6 - $ квадратичный невычет по модулю 7.

Че-то не понял.
Вы хотели сказать: взять по модулю 7, оттуда определить, что $x,y\equiv 0\pmod 7$, потом подставить и получить противоречие $7\mid 1$?

[iou]

Sonic86,
Я имел в виду следующее:
$2x^2-5y^2=7$, тогда $2x^2=5y^2 \mod 7$, но $5^{-1}=3 \mod 7$, тогда $6x^2=y^2 \mod 7$, то есть $6=t^2 \mod 7$

[Sonic86]

iou в сообщении #1193889 писал(а):

$6x^2=y^2 \mod 7$, то есть $6=t^2 \mod 7$

Вот этот переход работает не для всех $y$.

[iou]

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

Вот этот переход работает не для всех $y$.

Почему? Я думал, что он скорее работает не для всех $x$ (работает для всех ненулевых элементов $F_7$, т.к. они обратимы), но в случае $x=0$ имеем, что $y=0$ и тогда, как Вы и сказали, после подстановки оных в уравнение получаем $7 | 1$. Случай $y=0$ аналогичен, а для всех остальных пар $(x, y)$, где $x$ и $y$ ненулевые всё работает, казалось бы.

[Sonic86]

iou в сообщении #1193899 писал(а):

работает для всех ненулевых элементов $F_7$

Теперь согласен.

[Stensen]

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

Пусть надо решить диофантово уравнение $F=0$ - в $\mathbb{Z}$. А давайте порешаем его в $\mathbb{Z}_m$.
Можно было бы спросить - почему именно $\mathbb{Z}_m$? Ответ: потому что $\mathbb{Z}_m$ - это всевозможные ядра эпиморфизмов $\mathbb{Z}$, других (к сожалению или к счастью) нету.

Поясните пожалуйста, если можно "на пальцах", мозг пока тормозит. Почему решение диофантова уравнения в $\mathbb{Z}_m$ приводит к результату именно потому, что $\mathbb{Z}_m$ является ядром эпиморфизмов $\mathbb{Z}$?

[Sonic86]

Stensen в сообщении #1194294 писал(а):

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

Пусть надо решить диофантово уравнение $F=0$ - в $\mathbb{Z}$. А давайте порешаем его в $\mathbb{Z}_m$.
Можно было бы спросить - почему именно $\mathbb{Z}_m$? Ответ: потому что $\mathbb{Z}_m$ - это всевозможные ядра эпиморфизмов $\mathbb{Z}$, других (к сожалению или к счастью) нету.

Поясните пожалуйста, если можно "на пальцах", мозг пока тормозит. Почему решение диофантова уравнения в $\mathbb{Z}_m$ приводит к результату именно потому, что $\mathbb{Z}_m$ является ядром эпиморфизмов $\mathbb{Z}$?

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

[Stensen]

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

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

Спасибо, полегчало.