Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 28 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 24 дек 2013, 19:57 
Не в сети
Администратор
Аватара пользователя
Зарегистрирован:
23 фев 2010, 22:52
Сообщений: 6003
Cпасибо сказано: 3247
Спасибо получено:
3150 раз в 2273 сообщениях
Очков репутации: 652

Добавить очки репутацииУменьшить очки репутации
Нужен алгоритм сведения системы линейных сравнений с одним переменным к одному сравнению.
Нашёл такой вариант

[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].

Это верно?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 15:36 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
Alexdemath писал(а):
Это верно?

При условии [math](a_n,m_n)=1[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 16:11 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
15 май 2011, 10:27
Сообщений: 7856
Cпасибо сказано: 629
Спасибо получено:
7057 раз в 5487 сообщениях
Очков репутации: 317

Добавить очки репутацииУменьшить очки репутации
Может это пригодится.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 17:14 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Можете для контроля в Бухштабе глянуть.

Такое ощущение, что тут баг. Например,
[math]\begin{cases} x\equiv 1\pmod 3 \\ x\equiv 0\pmod 3 \end{cases}[/math]
по приведенной формуле преобразуется в сравнение, имеющее решение...
При [math](\forall i)a_i=1[/math] не получается утверждение КТО, а должно. Или получается?

Лучше КТО посмотреть...

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Sonic "Спасибо" сказали:
Alexdemath
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 17:50 
Не в сети
Администратор
Аватара пользователя
Зарегистрирован:
23 фев 2010, 22:52
Сообщений: 6003
Cпасибо сказано: 3247
Спасибо получено:
3150 раз в 2273 сообщениях
Очков репутации: 652

Добавить очки репутацииУменьшить очки репутации
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.

Я так понимаю, что дублирующие решения при сведении системы к одному сравнению уничтожаются?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 18:32 
Не в сети
Одарённый
Зарегистрирован:
25 окт 2011, 19:25
Сообщений: 124
Cпасибо сказано: 8
Спасибо получено:
27 раз в 26 сообщениях
Очков репутации: 6

Добавить очки репутацииУменьшить очки репутации
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]
Каждую дробь по соответствующему модулю можно заменить целым числом и получить китайскую теорему об остатках.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 18:44 
Не в сети
Администратор
Аватара пользователя
Зарегистрирован:
23 фев 2010, 22:52
Сообщений: 6003
Cпасибо сказано: 3247
Спасибо получено:
3150 раз в 2273 сообщениях
Очков репутации: 652

Добавить очки репутацииУменьшить очки репутации
Andrey A, а как на основе этого получить одно равносильное сравнение?

Решение системы не нужно, а только одно равносильное сравнение.

Если [math]a_i\ne0,~b_i\ne0[/math] и [math]m_i[/math] различны, то формула из моего 1-го поста верна?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 19:05 
Не в сети
Одарённый
Зарегистрирован:
25 окт 2011, 19:25
Сообщений: 124
Cпасибо сказано: 8
Спасибо получено:
27 раз в 26 сообщениях
Очков репутации: 6

Добавить очки репутацииУменьшить очки репутации
Простите, мне кажется, что выражение [math]M(...)\equiv M(...)\ \operatorname{mod}M[/math] всегда верно, что бы ни стояло в скобках, поскольку [math](...)[/math] опять-таки могут быть заменены целым числом. А китайская теорема об остатках как раз и сводит несколько сравнений по разным модулям к единому сравнению, верному по каждому модулю, а значит и по [math]M[/math].

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Andrey A "Спасибо" сказали:
Alexdemath
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 19:36 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Alexdemath писал(а):
Программная проверка решений множества систем подтверждают формулу. Однако при решении некоторых систем не ясно, сколько у них решений.

Например, такая система

[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]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]\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]\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]m_j[/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, то все верно. Если же исходна система решений не имеет, то....
А вот и нет: тогда неверно. И контрпример легко подбирается.
Значит система и Ваше сравнение равносильны тогда и только тогда, когда все модули попарно взаимно просты и система разрешима, равносильно тому, когда система имеет одно решение.

Короче, юзайте КТО :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Sonic "Спасибо" сказали:
Alexdemath
 Заголовок сообщения: Re: Сведение системы сравнений к одному сравнению
СообщениеДобавлено: 25 дек 2013, 20:34 
Не в сети
Администратор
Аватара пользователя
Зарегистрирован:
23 фев 2010, 22:52
Сообщений: 6003
Cпасибо сказано: 3247
Спасибо получено:
3150 раз в 2273 сообщениях
Очков репутации: 652

Добавить очки репутацииУменьшить очки репутации
Sonic писал(а):
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].
Это верно?
Верно тогда и только тогда, когда все модули [math]m_j[/math] попарно взаимно просты.

Однако в моём примере это условие не выполняется и по формуле получились верные решения (или это не все решения системы?).

То есть не совсем "тогда и только тогда"?

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2, 3  След.  Страница 1 из 3 [ Сообщений: 28 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Решение системы сравнений

в форуме MathCad

Olga_sh

10

655

26 фев 2020, 12:59

Найти решение системы сравнений

в форуме Численные методы

pomogite_reshit

1

341

03 мар 2021, 01:04

Как найти числа, удовлетворяющие сравнению?

в форуме Теория чисел

olgasikir

2

511

03 ноя 2016, 17:40

Оценка среднего в партии по сравнению с генеральным средним

в форуме Теория вероятностей

AnnaV

2

239

12 ноя 2017, 10:27

Сведение интеграла

в форуме Интегральное исчисление

Andrew42

4

514

14 июн 2016, 02:57

Сведение к криволинейному интегралу

в форуме Комплексный анализ и Операционное исчисление

Alena_Kovalenko

4

304

26 авг 2014, 13:13

Сведение к дифф. уравнению

в форуме Интегральное исчисление

Azerot

1

245

22 фев 2016, 14:28

Сведение к интегральному уравнению

в форуме Интегральное исчисление

Azerot

0

281

22 фев 2016, 14:34

Сведение к интегральному уравнению

в форуме Интегральное исчисление

Azerot

1

469

01 мар 2016, 00:28

Сведение к уравнению Пенлеве 2-го рода

в форуме Дифференциальные и Интегральные уравнения

Gargantua

0

246

18 янв 2017, 15:27


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved