Решение системы линейных сравнений от одного неизвестного

[main.c]

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

Joker_vD в сообщении #653195 писал(а):

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

Ааа, ясно, я как всегда узнал об этом последний

Joker_vD в сообщении #653195 писал(а):

э-э-э... не помню слова:

совокупности.
Кстати, зря Вы к совокупности переходите - букоф лишних много. Если $\text{НОД}(A,B,m)=D$, то Вы будете выписывать $D$ систем сравнений. Оно Вам надо?

main.c, есть такая древняя книжка Бухштаб Теория чисел. Возьмите ее, там линейные сравнения и системы линейных сравнений очень подробно разобраны в общем виде.

main.c в сообщении #653214 писал(а):

2. Коэффициент при $x$ и мод не взаимно просты.

Берем сравнение $Ax\equiv B\pmod m$. Ищем $d=\text{НОД}(A,B,m)$ (наведите мышкой на формулу, посмотрите, как она пишется). Полагаем $A'=\frac{A}{d}, B'=\frac{B}{d}, m'=\frac{m}{d}$ и тогда $Ax\equiv B\pmod m\Leftrightarrow A'x\equiv B'\pmod m'$ (по определению сравнений). Так что все сводится к случаю $\text{НОД}(A,B,m)=1$.
Снова рассмотрим сравнение $Ax\equiv B\pmod m$ уже с $\text{НОД}(A,B,m)=1$. Если теперь вдруг $\text{НОД}(A,m)=D>1$, то $m\mid Ax-B\Rightarrow D\mid Ax-B\Rightarrow D\mid B$, т.е. $D\mid \text{НОД}(A,B,m)$, что невозможно. Т.е. если вдруг $\text{НОД}(A,B,m)=1$, но $\text{НОД}(A,m)>1$, то решений нет.

main.c в сообщении #653214 писал(а):

1. Моды не взаимно просты

Если $D=\text{НОД}(m_1;m_2)$, то для существования решений сравнений $A_jx\equiv B_j\pmod{m_j}$ необходимо (и при выполнении условий выше (т.е. если каждое сравнение по отдельности имеет решение) вроде достаточно), чтобы система $A_jx\equiv B_j\pmod D, j=1;2$ имела решение (а ту уравнения проверяем на линейную зависимость и все).

Еще раз: это все изложено в Буштабе простым языком на нескольких страницах.

-- Пн дек 03, 2012 07:17:04 --

main.c в сообщении #653214 писал(а):

И вообще, какой критерий существования решений?

Наверное в случае системы с произвольным числом сравнений проверяем, что каждое сравнение имеет решение. Разлагаем модули на множители и проверяем сравнения и одинаковыми простыми в модулях на совместимость (хотя это немножко долго будет в случае больших чисел. В противном случае надо добавлять на каждом шаге одно сравнение, считать НОД-ы и проверять наличие решений и то...). Тут надо подумать немного (тем более, Вы же все в контексте алгоритма делаете). У вас произвольная система сравнений?

Спасибо за книжку).....она отличная