Изменения

<mathtex>a \equiv b(mod \text{ } m)</mathtex> <br><br>

*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>.

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

Согласно 10-му свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''.

Пусть <tex> (a, bm) = d </tex>. Сравнение <tex> ax \equiv b(mod \text{ }m)</tex> невозможно, если b не делится на '''d'''. При b, кратном '''d''', сравнение имеет '''d ''' решений.<br>'''Поиск решений:'''<br>

обозначим его <tex> a_dx \equiv b_d(mod \text{ } m_d)</tex>,. Пусть его решением будет <tex> x \equiv (-1)^x_0 </tex>, тогда остальные решения найдутся по следующей формуле: <tex> x_n = x_{n-1}P_{n-1}b_dm_d </tex>(mod \text{ } m_d)следует понимать, что <tex> x_i </tex>вычет по модулю, где поэтому в этой формуле можно сменить знак, для удобства), всего решений будет d. Если нахождение <tex> P_{n-1} x_0 </tex> - не является очевидным, то следует воспользоваться [[Цепная дробь | числитель подходящей дробитеорией цепных дробей]].Пусть , и тогда <tex> P x_0 = (-1)^{n-1}P_{n-1}b_d </tex> <br>После этого решения исходного сравнения запишутся так : <tex> x \equiv P; P+m_d; P+2m_d; \ldots ;P+dm_d (mod \text{ }m)</tex> == Китайская теорема об остатках == Пусть <tex> n = n_1 n_2 \ldots n_k </tex>, где <tex> n_i </tex> - попарно взаимно простые числа. Рассмотрим соответствие <tex> a \rightarrow (a_1 , a_2 , \ldots , a_k) </tex>, где <tex> a_i = a(mod \textP_{ }n)</tex>. Такое соответствие является однозначным, для любого '''а''' (<tex> 0 \le a \le n </tex>). <br>Неконструктивное доказательство : <br><tex> x-y \rightarrow (0 , 0 , \ldots , 0) \Leftrightarrow (x-y) \vdots m_i </tex>, значит <tex> x \equiv y(mod \text{ 1} \prod n_i )</tex>. То есть разных наборов всего n- [[Цепная дробь | числитель подходящей дроби]].

== Теорема Ферма = Примеры решения ==='''Пример 1.''' <br><tex> a^p 12x \equiv a6(mod \text{ }p18)</tex>, где '''p''' — простое.Доказательство.*1. <texbr> a \vdots pНайдем НОД </tex>(12, тогда, очевидно, 18)=6 </tex> a^p \vdots p</texbr>.*2. Рассмотрим случай '''a''' не кратного '''p'''. Рассмотрим приведенную систему вычетов Перейдем к новому сравнению <tex> r_1, r_2, 2x \ldots , r_{p-equiv 1} (3) </tex>.<br>Система Легко находится <tex> ar_1, ar_2, \ldots , ar_{p-1} x_0 = 2 </tex> задает те же вычеты, только в другом порядке,<br>таким образом Тогда ответом будет <tex> x_0 =2, x_1 = x_0 - \prod_frac{i=1m}^{p-1(a,m)} ar_i \equiv \prod_{i=1}^{p-1} r_i (mod \text{ }p) </tex>,сократив лишнее, получаем <tex> a^{px_2 = -1} \equiv 1(mod \text{ }p)4</tex>. Домножив обе части на '''a''', получим теорему в изначально представленном виде.

== Теорема Вильсона =='''pПример 2.''' — простое <br><tex> \Leftrightarrow (p-1)! 111x \equiv -175(mod \text{ }p321)</tex>Доказательство:* <texbr> \Leftarrow Найдем НОД </tex> Если '''p''' — не простое(111, тогда <tex> (p-1321)! \vdots p </tex> (кроме <tex> p = 4 3 </tex>),но -175 кратно 3, в любом случае, мы не получим.* значит имеем 3 решения <texbr> \Rightarrow </tex> Пусть <tex>x : 1 \le x \le p-1</tex>, для любого такого существует парный ему <tex> yПерейдем к новому сравнению </tex> такой, что <tex> xy 37x \equiv 125(mod \text{ }p107) </tex>. Может случиться, что для некоторых <mathbr>x</math> будет выполнено равенство Воспользуемся цепными дробями, в нашем случае <tex>xn=y</tex>. Тогда <tex> x^2 \equiv 4, p_{n-1(mod \text{ }p) = 26</tex>, значит <tex> x_0 \equiv -26\cdot 25 (x-1107)\equiv 99(x+1107) \vdots p </tex>, значит <texbr> x=1 Тогда ответом будет </tex> или <tex>xx_0 =p-1</tex>. Таким образом последовательность <tex> 299,3x_1 = 206, \ldots,p-2 x_2 = 313 </tex> разбивается на пары, что произведение чисел каждой из них сравнимо с 1 по модулю p. Таким образом <tex> (p-1)! \equiv 1(p-1)(mod \text{ }p)</tex>, откуда следует, что <tex> (p-1)! \equiv -1(mod \text{ }p)</tex>