Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 3 |
[ Сообщений: 28 ] | На страницу 1, 2, 3 След. |
|
Автор | Сообщение | ||
---|---|---|---|
Alexdemath |
|
||
Нашёл такой вариант [math]\left\{\!\begin{aligned}& a_1x \equiv b_1 \pmod{m_1}, \\& a_2x \equiv b_2 \pmod{m_2}, \\[-8pt] & ~\vdots \\[-6pt] & a_nx \equiv b_n \pmod{m_n},\end{aligned}\right.~ \Leftrightarrow~ M\sum\limits_{i=1}^{n}\frac{a_i}{m_i}\cdot x \equiv M\sum\limits_{i=1}^{n}\frac{b_i}{m_i} \pmod{M}[/math], где [math]M = \operatorname{NOK}(m_1,m_2,\ldots,m_n)[/math]. Это верно? |
|||
Вернуться к началу | |||
vorvalm |
|
||
Alexdemath писал(а): Это верно? При условии [math](a_n,m_n)=1[/math] |
|||
Вернуться к началу | |||
andrei |
|
||
Может это пригодится.
|
|||
Вернуться к началу | |||
Sonic |
|
||
Можете для контроля в Бухштабе глянуть.
Такое ощущение, что тут баг. Например, [math]\begin{cases} x\equiv 1\pmod 3 \\ x\equiv 0\pmod 3 \end{cases}[/math] по приведенной формуле преобразуется в сравнение, имеющее решение... При [math](\forall i)a_i=1[/math] не получается утверждение КТО, а должно. Или получается? Лучше КТО посмотреть... |
|||
Вернуться к началу | |||
За это сообщение пользователю Sonic "Спасибо" сказали: Alexdemath |
|||
Alexdemath |
|
||
Sonic, спасибо. Разбираю Ваш пример...
Программная проверка решений множества систем подтверждают формулу. Однако при решении некоторых систем не ясно, сколько у них решений. Например, такая система [math]\left\{\!\begin{aligned}-4x&\equiv14&&(\operatorname{mod}{58}),\\5x&\equiv55&&(\operatorname{mod}{10}),\\14x&\equiv-21&&(\operatorname{mod}{49}).\end{aligned}\right.[/math] Находим НОДы: [math]\begin{aligned}&d_{1}=\operatorname{NOD}(a_1,m_1)=\operatorname{NOD}(-4,58)=2\,,\\ &d_{2}=\operatorname{NOD}(a_2,m_2)=\operatorname{NOD}(5,10)=5\,,\\ &d_{3}=\operatorname{NOD}(a_3,m_3)=\operatorname{NOD}(14,49)=7\,.\end{aligned}[/math] Следовательно, система может иметь максимум [math]d_1\cdot d_2\cdot d_3=70[/math] решений (верно?). Далее, решая каждое уравнение системы по отдельности, имеем [math]\left\{\!\begin{aligned}x&\equiv 29k_{1}+ 11 && (\operatorname{mod}{58}),&&k_{1}\in\{0,1\},\\x&\equiv 2k_{2}+ 1 && (\operatorname{mod}{10}),&&k_{2}\in\{0,1,2,3,4\},\\x&\equiv 7k_{3}+ 2 && (\operatorname{mod}{49}),&&k_{3}\in\{0,1,\ldots,6\}.\end{aligned}\right.[/math] Если же решать по формуле, то система сведётся к сравнению [math]10185x \equiv 75495\!\!\pmod{14210}[/math], которое имеет 35 решений: [math]x_k\equiv 406k+359\pmod{14210},~k\in\{0,1,\ldots,34\}[/math], а не 70. Я так понимаю, что дублирующие решения при сведении системы к одному сравнению уничтожаются? |
|||
Вернуться к началу | |||
Andrey A |
|
||
Alexdemath писал(а): Нужен алгоритм сведения системы линейных сравнений с одним переменным к одному сравнению. Нашёл такой вариант [math]\left\{\!\begin{aligned}& a_1x \equiv b_1 \pmod{m_1}, \\& a_2x \equiv b_2 \pmod{m_2}, \\[-8pt] & ~\vdots \\[-6pt] & a_nx \equiv b_n \pmod{m_n},\end{aligned}\right.~ \Leftrightarrow~ M\sum\limits_{i=1}^{n}\frac{a_i}{m_i}\cdot x \equiv M\sum\limits_{i=1}^{n}\frac{b_i}{m_i}\pmod{M}, \quad M = \operatorname{NOK}(m_1,m_2,\ldots,m_n).[/math] Это верно? Вашу систему можно периписать так: [math]\left\{\!\begin{aligned}& x \equiv \frac{b_1}{a_1} \pmod{m_1}, \\& x \equiv \frac{b_2}{a_2} \pmod{m_2}, \\[-8pt] & ~\vdots \\[-6pt] & x \equiv \frac{b_n}{a_n} \pmod{m_n}[/math] Каждую дробь по соответствующему модулю можно заменить целым числом и получить китайскую теорему об остатках. |
|||
Вернуться к началу | |||
Alexdemath |
|
||
Andrey A, а как на основе этого получить одно равносильное сравнение?
Решение системы не нужно, а только одно равносильное сравнение. Если [math]a_i\ne0,~b_i\ne0[/math] и [math]m_i[/math] различны, то формула из моего 1-го поста верна? |
|||
Вернуться к началу | |||
Andrey A |
|
||
Простите, мне кажется, что выражение [math]M(...)\equiv M(...)\ \operatorname{mod}M[/math] всегда верно, что бы ни стояло в скобках, поскольку [math](...)[/math] опять-таки могут быть заменены целым числом. А китайская теорема об остатках как раз и сводит несколько сравнений по разным модулям к единому сравнению, верному по каждому модулю, а значит и по [math]M[/math].
|
|||
Вернуться к началу | |||
За это сообщение пользователю Andrey A "Спасибо" сказали: Alexdemath |
|||
Sonic |
|
|
Alexdemath писал(а): Программная проверка решений множества систем подтверждают формулу. Однако при решении некоторых систем не ясно, сколько у них решений. Ага. В общем виде это тоже верно: если [math]j[/math]-е сравнение [math]a_jx\equiv b_j\pmod{m_j}[/math] имеет [math]\gcd (a_j,b_j,m_j)=d_j[/math], то его можно равносильно сократить на [math]d_j[/math], а если вернуться от нового модуля [math]\frac{m_j}{d_j}[/math] к исходному, то получим [math]d_j[/math] решений сравнения. Всего это даст [math]N\cdot \prod\limits_{j=1}^s d_j[/math] решений, где [math]N[/math] - число решений системы сравнений [math](\forall j)\frac{a_j}{d_j}x\equiv \frac{b_j}{d_j}\pmod{\frac{m_j}{d_j}}[/math].Например, такая система [math]\left\{\!\begin{aligned}-4x&\equiv14&&(\operatorname{mod}{58}),\\5x&\equiv55&&(\operatorname{mod}{10}),\\14x&\equiv-21&&(\operatorname{mod}{49}).\end{aligned}\right.[/math] Находим НОДы: [math]\begin{aligned}&d_{1}=\operatorname{NOD}(a_1,m_1)=\operatorname{NOD}(-4,58)=2\,,\\ &d_{2}=\operatorname{NOD}(a_2,m_2)=\operatorname{NOD}(5,10)=5\,,\\ &d_{3}=\operatorname{NOD}(a_3,m_3)=\operatorname{NOD}(14,49)=7\,.\end{aligned}[/math] Следовательно, система может иметь максимум [math]d_1\cdot d_2\cdot d_3=70[/math] решений (верно?). Если все [math]\frac{m_j}{d_j}[/math] попарно взаимно просты, то можно от системы перейти сравнению [math]Ax\equiv B\pmod {\frac{M}{D}}[/math] по одному модулю, из которого потом можно получить все решения, они будут иметь задаваться сравнением [math]Ax\equiv B +k\frac{M}{D}\pmod M[/math] Alexdemath писал(а): Я так понимаю, что дублирующие решения при при сведении системы к одному сравнению уничтожаются? Ну если модуль не сокращать, то они теряются, а если сокращать - их потом можно обратно "вытащить" вышеописанным способом.Если все [math]m_j[/math] попарно взаимно просты, то должна быть эквивалентность (сейчас заставлю себя ручку взять). Если неверно, что все [math]m_j[/math] попарно взаимно просты, то этот случай надо как-то обработать с меньшими трудозатратами... Alexdemath писал(а): Решение системы не нужно, а только одно равносильное сравнение. В общем случае требование некорректно решение системы является равносильным ему сравнением. Уточните вопрос.Alexdemath писал(а): Нужен алгоритм сведения системы линейных сравнений с одним переменным к одному сравнению. Верно тогда и только тогда, когда все модули [math]m_j[/math] попарно взаимно просты.Нашёл такой вариант [math]\left\{\!\begin{aligned}& a_1x \equiv b_1 \pmod{m_1}, \\& a_2x \equiv b_2 \pmod{m_2}, \\[-8pt] & ~\vdots \\[-6pt] & a_nx \equiv b_n \pmod{m_n},\end{aligned}\right.~ \Leftrightarrow~ M\sum\limits_{i=1}^{n}\frac{a_i}{m_i}\cdot x \equiv M\sum\limits_{i=1}^{n}\frac{b_i}{m_i} \pmod{M}[/math], где [math]M = \operatorname{NOK}(m_1,m_2,\ldots,m_n)[/math]. Это верно? [math]\Leftarrow[/math]: берем сравнение справа по модулю [math]m_j[/math], получаем [math]m_j\frac{a_j}{m_j}x\equiv m_j\frac{b_j}{m_j}\pmod{m_j}[/math] [math]\Rightarrow[/math]: [math]a_jx\equiv b_j\pmod{m_j}\Leftrightarrow a_j\frac{M}{m_j}x\equiv b_j\frac{M}{m_j}\pmod{M}[/math], суммируя по [math]j[/math] получаем правую часть. Полученное сравнение имеет не более одного решения. С другой стороны, поскольку все [math]m_j[/math] взаимно просты, то эквивалентное сравнение также имеет не более одного решения: одно решение - если каждое сравнение разрешимо и нуль сравнений, если хотя бы одно сравнение неразрешимо. Если число решений системы сравнения =1, то все верно. Если же исходна система решений не имеет, то.... А вот и нет: тогда неверно. И контрпример легко подбирается. Значит система и Ваше сравнение равносильны тогда и только тогда, когда все модули попарно взаимно просты и система разрешима, равносильно тому, когда система имеет одно решение. Короче, юзайте КТО |
||
Вернуться к началу | ||
За это сообщение пользователю Sonic "Спасибо" сказали: Alexdemath |
||
Alexdemath |
|
|
Sonic писал(а): Alexdemath писал(а): Нужен алгоритм сведения системы линейных сравнений с одним переменным к одному сравнению. Верно тогда и только тогда, когда все модули [math]m_j[/math] попарно взаимно просты.Нашёл такой вариант [math]\left\{\!\begin{aligned}& a_1x \equiv b_1 \pmod{m_1}, \\& a_2x \equiv b_2 \pmod{m_2}, \\[-8pt] & ~\vdots \\[-6pt] & a_nx \equiv b_n \pmod{m_n},\end{aligned}\right.~ \Leftrightarrow~ M\sum\limits_{i=1}^{n}\frac{a_i}{m_i}\cdot x \equiv M\sum\limits_{i=1}^{n}\frac{b_i}{m_i} \pmod{M}[/math], где [math]M = \operatorname{NOK}(m_1,m_2,\ldots,m_n)[/math]. Это верно? Однако в моём примере это условие не выполняется и по формуле получились верные решения (или это не все решения системы?). То есть не совсем "тогда и только тогда"? |
||
Вернуться к началу | ||
На страницу 1, 2, 3 След. | [ Сообщений: 28 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Решение системы сравнений
в форуме MathCad |
10 |
655 |
26 фев 2020, 12:59 |
|
Найти решение системы сравнений
в форуме Численные методы |
1 |
341 |
03 мар 2021, 01:04 |
|
Как найти числа, удовлетворяющие сравнению?
в форуме Теория чисел |
2 |
511 |
03 ноя 2016, 17:40 |
|
Оценка среднего в партии по сравнению с генеральным средним
в форуме Теория вероятностей |
2 |
239 |
12 ноя 2017, 10:27 |
|
Сведение интеграла
в форуме Интегральное исчисление |
4 |
514 |
14 июн 2016, 02:57 |
|
Сведение к криволинейному интегралу | 4 |
304 |
26 авг 2014, 13:13 |
|
Сведение к дифф. уравнению
в форуме Интегральное исчисление |
1 |
245 |
22 фев 2016, 14:28 |
|
Сведение к интегральному уравнению
в форуме Интегральное исчисление |
0 |
281 |
22 фев 2016, 14:34 |
|
Сведение к интегральному уравнению
в форуме Интегральное исчисление |
1 |
469 |
01 мар 2016, 00:28 |
|
Сведение к уравнению Пенлеве 2-го рода | 0 |
246 |
18 янв 2017, 15:27 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |