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

[main.c]

$$ \left\{ \begin{aligned} 10x = 12 \mod 14\\ 2x = 3 \mod 5 \end{aligned} \right. $$

Преобразуя эту систему получаю:

$$ \left\{ \begin{aligned} x = 4 \mod 14\\ x = 4 \mod 5 \end{aligned} \right. $$

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

[Joker_vD]

Ну, как-как... Пусть есть система $\{x\equiv a_i\pmod{m_i}$, и $(m_i,m_j)=1$ при $i\ne j$. Обозначим $M=m_1m_2\dots m_n$, $M_i=\frac{M}{m_i}$, найдем $M'_i$ такие, что $M_iM'_i\equiv1\pmod{m_i}$; тогда $x \equiv \sum\limits_{i=1}^n M_iM'_ia_i\pmod M$.

-- Вс дек 02, 2012 20:16:53 --

Хотя в вашем случае и так видно, что $x=4$ подходит.

[main.c]

Хорошо, а как найти $M'$?

[Joker_vD]

Ну, если вам действительно это так надо... В нашем случае $M=70$, $M_1=5$, $M_2=14$ и мы решаем $5M'_1\equiv 1\pmod{14}$.

$5=1\cdot5+0\cdot 14,\quad14=0\cdot5+1\cdot14$. Вычитаем из второго два раза первое, получаем $4=-2\cdot5+1\cdot14$, теперь вычитаем полученное из первого равенства и получаем $1=3\cdot5-1\cdot14$ — т.е. $3\cdot5\equiv1\pmod{14}$, $M'_1=3$.

И только что мы еще нашли $M'_2=-1$. Что ж, собираем все в кучу: $x=5\cdot3\cdot4+14\cdot(-1)\cdot4=4$.

[main.c]

$4 + 70t$ или $4 + 35t$ , где $t$ целое число?

[Joker_vD]

$4+70t$. Как вы легко можете заметить, $39\equiv11\pmod{14}$.

[main.c]

Я хочу понять полный алгоритм действий, потому что мне надо это запрограммировать.

-- 02.12.2012, 19:51 --

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

$4+70t$. Как вы легко можете заметить, $39\equiv11\pmod{14}$.

А вы подставьте в изначальное уравнение и получите правильное тождество.

[Joker_vD]

А, вы ж неправильно преобразовали. Как вы от $10x\equiv12\pmod{14}$ перешли к $x\equiv4\pmod{14}$? Почему не к $x\equiv11\pmod{14}$?

[Sonic86]

Вообще-то от сравнение $10x\equiv12\pmod{14}$ эквивалентно $5x\equiv 6\pmod{7}$

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

Хорошо, а как найти $M'$?

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

Обозначим $M=m_1m_2\dots m_n$, $M_i=\frac{M}{m_i}$, найдем $M'_i$ такие, что $M_iM'_i\equiv1\pmod{m_i}$;

Это фактически решение сравнения вида $Ay\equiv 1\pmod m$ с неизвестным $y$ и известными $A,m$. Решается она алгоритмом Евклида. Где-то bot показывал очень простой способ решения линейного уравнения алгоритмом Евклида...

-- Вс дек 02, 2012 18:15:30 --

Блин, я не нашел сообщения bot-а, попробую воспроизвести. Обычно алгоритм Евклида описывается как двухпроходный:
1) сначала ищем НОД, по ходу дела записываем преобразования;
2) обращаем последовательность преобразований в поиске НОД, в результате находим переменные.
А у bot-а был однопроходный вариант. Типа такого:
Сравнение $Ay\equiv 1\pmod m\Leftrightarrow Ay-mz=1, y,z\in\mathbb{Z}$. Ставим уравнению в соответствие матрицу $\binom{A \ y}{m \ z}$. Левый столбец матрицы известен, правый - нет. Уравнение можно равносильно преобразовать так:
$(A-m)y-m(z-y)=1$ - ему соответствует матрица $\binom{A-m \ y}{m \ z-y}$. Т.е. мы можем выполнять преобразование
$\binom{A \ y}{m \ z} \to \binom{A-m \ y}{m \ z-y}$
И аналогичное 2-е преобразование тоже надо допустить. Выполняя поиск НОД в левом столбце, в конце концов получим матрицу $\binom{C \ L}{1 \ M}$, откуда $M=1, L=0$, где $M,L$ - некие линейные комбинации от $y,z$. Уравнение $L=0\Leftrightarrow Py-Qz=0$ - берем у него решения $y=Q, z=P$. Всё.

[Joker_vD]

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

main.c
При решении системы вам, чтобы воспользоваться КТО, надо свести все сравнения $kx\equiv a\pmod m$ к виду $x\equiv a'\pmod m$, без коэффициента при $x$. Фишка в том, что у сравнения $kx\equiv a\pmod m$ может быть несколько решений, так что ваша исходная система эквивалентна вот такой э-э-э... не помню слова:

$$\left[\begin{array}{ll} \left\{\begin{array}{rcll}x&\equiv&4&\pmod{14}\\x&\equiv&4&\pmod5\end{array}\right. \\ \vphantom=\\ \left\{\begin{array}{rcll}x&\equiv&11&\pmod{14}\\x&\equiv&4&\pmod5\end{array}\right. \end{array}\right.$$

[main.c]

Так, программу я почти написал, осталось уточнить имеет ли эта система решения, если:
1. Моды не взаимно просты
2. Коэффициент при $x$ и мод не взаимно просты.
И вообще, какой критерий существования решений?

-- 02.12.2012, 22:44 --

если $a$ делится на НОД($k,m$) решение существует, так ведь или я ошибаюсь?

[Sonic86]

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 писал(а):

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

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

[nnosipov]

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

Берем сравнение $Ax\equiv B\pmod m$. Ищем $d=\text{НОД}(A,B,m)$ ...

Обычно ищут $d=\text{НОД}(A,m)$.

[main.c]

На вход подаются 2 сравнения вида $Ax\equiv B\pmod m$, которые составляют систему.
Теперь как работает алгоритм:
1. По возможности сокращаем уравнения, к примеру было $ 10x = 12 \mod 14$, а стало $5x = 6 \mod 7$.
2. $d=\text{НОД}(A,m)$, если $B$ делится на $d$, то всё хорошо и мы сможем привеcти это уравнение к виду $x\equiv B'\pmod m$,
а если нет, то система решений не имеет.
3. Если $B'_1 == B'_2$, ответ $x = m_1m_2t + B'_1$,
а иначе запускаем расширенный алгоритм Евклида для чисел$m_1, m_2$, из которого в случае если они взаимно просты мы получим числа $k_1$ и $k_2$, такие , что $k_1m_1 + k_2m_2 = 1$. Первое уравнение можно переписать в виде $x = B'_1 + t_1m_1$, аналогично второе, приравняв правые части и сделав некоторые переносы получим диофантово уравнение $t_1m_1 - t_2m_2 = B'_2 - B'_1$, домножив уравнение получившееся из алгоритма Евклида на $ B'_2 - B'_1$ получим $(B'_2 - B'_1)k_1m_1 +(B'_2 - B'_1)k_2m_2 = B'_2 - B'_1$, значит можем записать $t_1 = (B'_2 - B'_1)k_1 $
4.Подставив $t_1$ в $x = B'_1 + t_1m_1$ получим одно из решений этой системы, обозначим его $x_0$, тогда все решения будут иметь вид $x = x_0 + m_1m_2t$.
Вопрос, а что делать, если в 3 шаге $m_1$ и $m_2$ не взаимно просты, простите за повторный вопрос, но мне хочется узнать, смогу ли я тогда найти решение снова через евклида и диофантово уравнение?

[nnosipov]

main.c, я бы сначала решил первое сравнение $A_1x \equiv B_1 \pmod{m_1}$, а потом найденное решение $x=\alpha y+\beta$ (если, конечно, оно будет) подставил бы во второе сравнение $A_2x \equiv B_2 \pmod{m_2}$ и затем бы решил это второе сравнение относительно нового неизвестного $y$. А у Вас что-то много всего. Здесь главное --- осознать, как решить одно сравнение.