1632
правки
Изменения
м
{{В разработке}}
== Теорема Вильсона =='''pПример 2.''' — простое <br><tex> 111x \equiv 75(mod \text{ }321)</tex> <br>Найдем НОД <tex>(111,321)=3 </tex> , 75 кратно 3, значит имеем 3 решения <br>Перейдем к новому сравнению <tex> 37x \Leftrightarrow equiv 25(p107) </tex> <br>Воспользуемся цепными дробями, в нашем случае <tex> n=4, p_{n-1} = 26</tex>, значит <tex> x_0 \equiv -26\cdot 25 (107)! \equiv -199(mod text{ }p107)</tex><br>Тогда ответом будет <tex> x_0 = 99, x_1 = 206, x_2 = 313 </tex>.
rollbackEdits.php mass rollback
== Сравнения по модулю ==
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число '''m''', которое назовем модулем.
Каждому целому числу отвечает определенный остаток от деления его на '''m'''. Если двум целым '''a''' и '''b''' отвечает один и тот же остаток '''r''', то они называются сравнимыми по модулю '''m'''.<br><br>
Сравнимость для '''a''' и '''b''' записывается так : <br>
<mathtex>a \equiv b(mod \text{ } m)</mathtex> <br><br>
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
*1а. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t {{--- }} целое.*2б. Делимости <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>.<br>** Обратно, из <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>.
** Следует из пункта "а" по свойству [[Наибольший общий делитель|НОДа]].
== Полная и приведенная система вычетов ==
называется '''наименьшим неотрицательным вычетом'''.<br><br>
Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю.<br><br>
Согласно 10-му свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''.
== Решение линейных систем по модулю ==
Пусть <tex> (a, m) == Теорема Ферма ==d </tex>. Сравнение <tex> a^p ax \equiv ab(mod \text{ }pm)</tex>невозможно, где если b не делится на '''d'''. При b, кратном '''d''', сравнение имеет '''pd''' — простоерешений.<br>Доказательство.'''Поиск решений:'''<br>*1. <tex> a ax \equiv b(mod \vdots ptext{ }m)</tex>, тогда, очевидно<tex> (a, b) = d </tex> <br>Составим новое сравнение <tex> \frac{a^p }{d}x \equiv \frac{b}{d}(mod \text{ } \vdots pfrac{m}{d})</tex>.,*2. Рассмотрим случай '''a''' не кратного '''p'''. Рассмотрим приведенную систему вычетов обозначим его <tex> r_1, r_2, a_dx \equiv b_d(mod \ldots , r_text{p-1} m_d)</tex>.Система Пусть его решением будет <tex> x_0 </tex> ar_1, ar_2, \ldots , ar_тогда остальные решения найдутся по следующей формуле: <tex> x_n = x_{pn-1} - m_d </tex>(следует понимать, что <tex> x_i </tex> задает те же вычетывычет по модулю, только поэтому в другом порядкеэтой формуле можно сменить знак, для удобства),таким образом всего решений будет d. Если нахождение <tex> x_0 </tex> не является очевидным, то следует воспользоваться [[Цепная дробь|теорией цепных дробей]], и тогда <tex> \prod_{ix_0 =(-1})^{pn-1} ar_i \equiv \prod_P_{i=n-1}^b_d</tex>, где <tex> P_{pn-1} r_i </tex> - [[Цепная дробь | числитель подходящей дроби]]. === Примеры решения ==='''Пример 1.''' <br><tex> 12x \equiv 6(mod \text{ }p18) </tex><br>Найдем НОД <tex>(12,18)=6 </tex> <br>сократив лишнее, получаем Перейдем к новому сравнению <tex> a^{p-1} 2x \equiv 1(mod 3) </tex> <br>Легко находится <tex> x_0 = 2 </tex> <br>Тогда ответом будет <tex> x_0 =2, x_1 = x_0 - \textfrac{ m}p{(a,m)}=-1, x_2 = -4</tex>. Домножив обе части на '''a''', получим теорему в изначально представленном виде.
