В натуральных числах

[Andrey A]

Для фиксированного нечетного составного $M$ что можно сказать о количестве решений системы
$\begin{cases} x+y+z+t=M \\ xy\equiv zt \pmod M \end{cases}$
кроме того, что оно конечно?

[Null]

Решений всегда бесконечное число.

[ex-math]

Ну как же, когда их тривиально меньше $M^3$.

[ИСН]

$t=M-x-y-z$
$xy\equiv z(M-x-y-z)$
$xy+z(x+y+z)\equiv0$
$xy+xz+yz+z^2\equiv0$
$(x+z)(y+z)\equiv0$
всё?

[ex-math]

ИСН
А что -- всё? Получается $O(M^{2+\varepsilon})$?

[Andrey A]

Null в сообщении #877365 писал(а):

Решений всегда бесконечное число.

В целых - да, но не в натуральных. Для $M=9$ всего два решения, если не считать $0 \in \mathbb {N}$:

$5\cdot 2\equiv 1\cdot 1$

$2\cdot 2\equiv 1\cdot 4$

[ИСН]

ex-math в сообщении #877387 писал(а):

А что -- всё? Получается $O(M^{2+\varepsilon})$?

Я думал, в таком виде уже что-то известно точно. Но во-первых, не очень-то, а во-вторых, там ещё не любое $z$ подходит (из-за противоестественного требования, чтобы сумма была не кратна, а именно равна $M$). Хотя всё равно, кажется, это быстрее, чем $2+\varepsilon$.

-- менее минуты назад --

Слушайте, это не какой-нибудь Project Euler опять?

[ex-math]

Ну вроде можно без $\varepsilon$.
Что же все-таки от нас хотят? Не очень понятно.

-- 20.06.2014, 00:39 --

Не, $\tau$ все равно пролезает

[Andrey A]

ИСН в сообщении #877383 писал(а):

всё?

Все. Для $M=m_1m_2$ и достаточно малого произвольного $z$
$x\equiv -z\mod m_1$
$y\equiv -z\mod m_2$, хотя можно еще исходить из пар квадратов, сравнимых по $\mod M$, поскольку $(x-y)^2\equiv (z-t)^2$. Отсюда для простого $M$ количество решений - $0$, а с остальным пока не ясно.

-- 20.06.2014, 01:41 --

ex-math в сообщении #877391 писал(а):

Что же все-таки от нас хотят? Не очень понятно.

У меня нет точного ответа. Если это против правил раздела, то не обессудьте.

[ИСН]

Да откуда два-то? Для любого разложения M на множители (это даёт $\tau$) перебираем все пары чисел, кратных первому и второму множителю, соответственно. Первых будет столько, каков второй множитель, вторых - столько, каков первый, а всего пар, стало быть - как раз M. (Нужны ещё какие-то средства отсекания повторов, но асимптотики они не улучшат.) Эти числа - наши $x+z$ и $y+z$, т.е. по ним сразу видно, какие (достаточно большие, но также и достаточно маленькие) z можно брать.

[ex-math]

Для каждой пары, задав $z$, определим все остальное однозначно. Но способов выбрать $z$ будет порядка $M$, разве нет?

[ИСН]

Ну да, а что? $z$ задаётся двумя неравенствами, т.е. годятся все значения в каком-то диапазоне. Их количество мы находим мгновенно.

-- менее минуты назад --

Погодите, или мы о разном? Вы - о числе решений, что ли? Тогда всё ОК. Я-то говорил о трудоёмкости его нахождения.

[ex-math]

Да, о числе решений. Мне это казалось само собой разумеющимся Сила привычки.

[Andrey A]

Кое-что добавлю.
Если четверка $x,y;z,t$ - решение системы, то четверки
$x+1,y+1;z-1,t-1$
$x-1,y-1;z+1,t+1$ - тоже решения. Поэтому каждое решение заключено в арифметическую прогрессию между двумя "нулевыми" решениями. Пример для $M=15$:

$$\begin{matrix} 7,0;5,3\\ 8,1;4,2\\ 9,2;3,1\\ 10,3;2,0 \end{matrix}$$

Для простых $m_1, m_2$ количество искомых решений в такой прогрессии равно $y+t-1$ (если условиться $x>y;z>t$), а количество возможных прогрессий - $\frac{(m_1-1)(m_2-1)}{4}$. Почему это происходит - не очень понятно, тут связь с количеством "нулевых" решений, которые имеют вид $k_1m_1,k_2m_2;M-k_1m_1-k_2m_2,0$. Можно отсюда вывести выражение для общего числа решений системы при простых $m_1, m_2$:

$$N=\frac{(m_1^2-1)(m_2^2-1)}{24}-\frac{(m_1-1)(m_2-1)}{4}$$

Доказать не берусь, но если формула верна, верны также следующие утверждения:
- Для попарно вз. простых $A,B,C\ (AB>C)$ в натуральных числах разрешимо ровно одно из двух уравнений:
$AX+BY=C\ \ \ \ \ \ \ \ \ \ (1)$
$AX+BY=AB-C\ \ (2)$
- В случае простых $A,B$ для $C$ однозначно определено $C'< AB$ противоположной четности такое, что $C^2 \equiv C'^2 \mod {AB}$. Тогда если $C+C'>AB$, то для чисел $C,C'$ разрешимо уравнение (1), в противном случае - уравнение (2). Сумма всех $C_i$, не превышающих $AB$, для которых разрешимо уравнение (1) $S=\frac{(A-1)(B-1)(4AB+A+B+1)}{12}$. Сумма всех чисел, не превышающих $AB$, для которых разрешимо ур. (2) $s=\frac{(A-1)(B-1)(2AB-A-B-1)}{12}$.
Или я сильно ошибаюсь.

[Shadow]

Andrey A в сообщении #878108 писал(а):

- Для попарно вз. простых $A,B,C\ (AB>C)$ в натуральных числах разрешимо ровно одно из двух уравнений:
$AX+BY=C\ \ \ \ \ \ \ \ \ \ (1)$
$AX+BY=AB-C\ \ (2)$

Можно доказать проще. При таких условиях обе уравнения имеют решений в целых числах
$\\x=x_0-bk\\ y=y_0+ak$\\ k \in Z
где $x_0,y_0$ - некоторое решение.
Если $(x,y)$ решение первого уравнения, то $(b-x,-y)$ - решение второго: $a(b-x)-by=ab-ax-by=ab-c$
1. Если первое уравнение имеет решение в натуральных числах, то второе не имеет.
Пусть $x>0,y>0$ - некоторое решение первого уравнения. Все решения второго можно записать как $X=b-x-kb,\quad Y=-y+ka$
Тогда при $k \le 0, Y<0$, а при $k>0, X<0$
2. Если первое уравнение неразрешимо в натуральных числах, то второе разрешимо.
Пусть $(x,y)$ решение первого уравнения с наименьшим положительным $x\in (0,b)$. Если неразрешимо, то $y<0$.
Тогда $X=b-x,Y=-y$ решение второго.