Сравнения, система вычетов, решение линейных систем по модулю

2012-03-25T14:16:53Z

178.64.154.96: /* Свойства сравнений */

== Сравнения по модулю ==
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число '''m''', которое назовем модулем.
Каждому целому числу отвечает определенный остаток от деления его на '''m'''. Если двум целым '''a''' и '''b''' отвечает один и тот же остаток '''r''', то они называются сравнимыми по модулю '''m'''. 
Сравнимость для '''a''' и '''b''' записывается так : 
<tex>a \equiv b(mod \text{ } m)</tex> 
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
*а. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t {{---}} целое.
*б. Делимости <tex>\Huge{a - b}</tex> на '''m'''.
** Действительно, из <tex> a \equiv b(mod \text{ } m) </tex> следует <tex> a = mq + r, \text{ } b = mq_1 + r </tex>, откуда <tex> a - b = m(q-q_1)</tex>, и <tex> a = b + mt</tex>, где <tex> t = q - q_1</tex>. 
** Обратно, из <tex>\Huge{a = b + mt}</tex>, представляя '''b''' в форме <tex> b = mq_1 + r </tex>, выводим <tex> a = mq + r </tex>, где <tex> q = q_1 + t </tex>, значит <tex> a \equiv b(mod \text{ } m) </tex>.
== Арифметика сравнений ==

=== Свойства сравнений ===
*1. Два числа, сравнимые с третьим сравнимы между собой. <tex>a \equiv c(mod \text{ }m) \text{, } b \equiv c(mod \text{ }m) \Rightarrow a \equiv b(mod \text{ }m)</tex>
** Легко выводится из пункта "а".

*2. Сравнения можно почленно складывать. <tex> a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text{ }m)</tex>
** Представляем сравнения, как в пункте "а" и складываем.

*3. Сравнения можно почленно перемножать. <tex> a_1a_2a_3 \equiv b_1b_2b_3(mod \text{ }m)</tex>
** Представляем сравнения, как в пункте "а", перемножаем, получим <tex> a_1a_2a_3 = b_1b_2b_3+mN</tex>, где N{{---}}целое.

*4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
** Действительно, из <tex>a \equiv b(mod \text{ } m)</tex>, <tex> a = a_1d, b = b_1d, (d,m)=1</tex> следует, что <tex> a-b = (a_1 - b_1)d \vdots m </tex>, поэтому <tex> a_1 \equiv b_1(mod \text{ } m)</tex>.

*5. Обе части сравнения можно умножить на одно и тоже число.
** Действительно, из <tex>a \equiv b(mod \text{ } m)</tex>, следует <tex> a = b+mt, ak =bk +mkt </tex>, и, следовательно, <tex>ak \equiv bk(mod \text{ } mk)</tex>.

*6. Обе части сравнения и модуль можно разделить на их общий делитель.
** Действительно, пусть <tex>a \equiv b(mod \text{ } m), a = a_1d, b=b_1d, m=m_1d</tex>, отсюда <tex> a= b+mt, a_1d =b_1d +m_1dt, a_1 =b_1 +m_1t</tex>, и, следовательно, <tex>a_1 \equiv b_1(mod \text{ } m_1)</tex>.

*7. Если сравнение <tex>a\equiv b</tex> имеет место по нескольким модулям, то оно имеет место и по модулю равному [[Наименьшее общее кратное|НОК]] этих модулей.
**В самом деле, из <tex> a \equiv b(mod \text{ }m_1),\ldots,a \equiv b(mod \text{ }m_k)</tex> следует, что разность <tex> a-b </tex> делится на все модули <tex> m_1,m_2,\ldots,m_k</tex>. Поэтому она должна делиться и на их [[Наименьшее общее кратное|НОК]].

*8. Если сравнение имеет место по модулю '''m''', то оно имеет место и по модулю '''d''', равному любому делителю числа '''m'''.
** Следует из пункта "б".

*9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делиться на это число.
** Следует из пункта "а".

*10. Если <tex>a \equiv b(mod \text{ }m) </tex>, то <tex>(a,m) = (b,m) </tex>.
** Следует из пункта "а" по свойству [[Наибольший общий делитель|НОДа]].

== Полная и приведенная система вычетов ==
Числа равноостаточные(сравнимые по модулю '''m''') образуют класс чисел по модулю '''m'''.
Из такого определения следует, что всем числам класса отвечает один остаток '''r''', и мы получим все числа класса,
если в форме <tex>mt + r </tex> заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел. 
Любое число класса называется '''вычетом''' по модулю '''m'''. Вычет получаемый при <tex> t = 0</tex>, равный самому остатку '''r''',
называется '''наименьшим неотрицательным вычетом'''. 
Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю. 
Согласно 10 свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''.

== Решение линейных систем по модулю ==
Пусть <tex> (a, m) = d </tex>. Сравнение <tex> ax \equiv b(mod \text{ }m)</tex> невозможно, если b не делится на '''d'''. При b, кратном '''d''', сравнение имеет '''d''' решений. 
'''Поиск решений:''' 
<tex> ax \equiv b(mod \text{ }m)</tex>, <tex> (a, b) = d </tex> 
Составим новое сравнение <tex> \frac{a}{d}x \equiv \frac{b}{d}(mod \text{ } \frac{m}{d})</tex>,
обозначим его <tex> a_dx \equiv b_d(mod \text{ } m_d)</tex>. Пусть его решением будет <tex> x_0 </tex>, тогда остальные решения найдутся по следующей формуле: <tex> x_n = x_{n-1} - m_d </tex>(следует понимать, что <tex> x_i </tex> вычет по модулю, поэтому в этой формуле можно сменить знак, для удобства), всего решений будет d. Если нахождение <tex> x_0 </tex> не является очевидным, то следует воспользоваться [[Цепная дробь|теорией цепных дробей]], и тогда <tex> x_0 = (-1)^{n-1}P_{n-1}b_d</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]].

=== Примеры решения ===
'''Пример 1.''' 
<tex> 12x \equiv 6(mod \text{ }18)</tex> 
Найдем НОД <tex>(12,18)=6 </tex> 
Перейдем к новому сравнению <tex> 2x \equiv 1(3) </tex> 
Легко находится <tex> x_0 = 2 </tex> 
Тогда ответом будет <tex> x_0 =2, x_1 = x_0 - \frac{m}{(a,m)}=-1, x_2 = -4</tex>

'''Пример 2.''' 
<tex> 111x \equiv 75(mod \text{ }321)</tex> 
Найдем НОД <tex>(111,321)=3 </tex>, 75 кратно 3, значит имеем 3 решения 
Перейдем к новому сравнению <tex> 37x \equiv 25(107) </tex> 
Воспользуемся цепными дробями, в нашем случае <tex> n=4, p_{n-1} = 26</tex>, значит <tex> x_0 \equiv -26\cdot 25 (107) \equiv 99(107) </tex> 
Тогда ответом будет <tex> x_0 = 99, x_1 = 206, x_2 = 313 </tex>.

Викиконспекты - Вклад участника [ru]

Сравнения, система вычетов, решение линейных систем по модулю