Изменения

<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)^{n-1}P_{n-1}b_d(mod \text{ } m_d)x_0 </tex>, где <tex> P_{n-1} тогда остальные решения найдутся по следующей формуле: </tex> - [[Цепная дробь | числитель подходящей дроби]].Пусть <tex> P x_n = (-1)^x_{n-1}P_{n-1}b_d m_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 x_i </tex> - попарно взаимно простые числа. Рассмотрим соответствие <tex> a \rightarrow (a_1 вычет по модулю, a_2 , \ldots , a_k) </tex>, где <tex> a_i = a(mod \text{ }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{ } \prod n_i )</tex>. То есть разных наборов всего nрешений будет d. == Теорема Ферма == {{Теорема|id=thFerma|author=Ферма|about=a в степени p по модулю p.|statement= Если нахождение <tex> a^p \equiv a(mod \text{ }p)x_0 </tex>не является очевидным, где '''p''' — простое.то следует воспользоваться [[Цепная дробь|proof= *1. <tex> a \vdots p</tex>теорией цепных дробей]], и тогда, очевидно, <tex> a^p \vdots p</tex>.*2. Рассмотрим случай '''a''' не кратного '''p'''. Рассмотрим приведенную систему вычетов <tex> r_1, r_2, \ldots , r_{px_0 = (-1} </tex>.Система <tex> ar_1, ar_2, \ldots , ar_{p-1} </tex> задает те же вычеты, только в другом порядке,таким образом <tex> \prod_{i=1})^{pn-1} ar_i \equiv \prod_P_{i=1}^{pn-1} r_i (mod \text{ }p) b_d</tex>,сократив лишнее, получаем где <tex> a^P_{pn-1} \equiv 1(mod \text{ }p)</tex>- [[Цепная дробь | числитель подходящей дроби]]. Домножив обе части на '''a''', получим теорему в изначально представленном виде. }} == Теорема Вильсона ==

{{Теорема|id=thVilson|author=Вильсон|about=О простых числах|statement='''pПример 2.''' — простое <br><tex> \Leftrightarrow (p-1)! 111x \equiv -175(mod \text{ }p321)</tex>.|proof=* <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>}}