Модуле буйынса сағыштырыу битенең сығанаҡ тексын ҡарарға

Натураль һанды '''мо́дуле буйынса сағыштырыу '''<math>m</math> шуны күрһәтә: һайлап алған ике бөтөн һан <math>m</math>-ға бүлгәндә бер үк ҡалдыҡ бирә. [[Бөтөн һан]] <math>m</math>-дан күберәк булмаған ҡалдыҡтар бирә. Тимәк, бөтә бөтөн һандарҙы <math>m</math>-ға ҡарата <math>m</math> төркөмгә бүлергә мөмкин, һәр төркөм <math>m</math>-ға бүлгәндәге билдәле бер ҡалдыҡҡа тура килә.

'''Мо́дулле арифме́тика''', йыш ҡына '''модуля́р арифметика''' тип атала<ref>{{книга |автор=Вельшенбах М.|часть=Глава 5. Модулле математика: вычисление в классах вычетов.| ответственный=|заглавие=Криптография на Си и С++ в действии.|место=М. |нәшриәт=«Триумф»|йыл=2004|том=|биттәр=81—95|страниц=464 |isbn=5-89392-083-X|ссылка=}}</ref><ref>{{cite web|url=http://www.computer-museum.ru/histussr/sokconf0.htm|title=Халыҡ-ара фәнни конференция материалдары “Модуляр арифметика”|date=2005|publisher=Виртуаль компьютер музейы|accessdate=2010-07-31}}</ref> математикала, информатикала һәм криптографияла киң ҡулланыла<ref>{{статья |автор=Егоров А. А.|ссылка=http://kvant.mccme.ru/1970/05/sravneniya_po_modulyu_i_arifme.htm |заглавие=Модуле буйынса сағыштырыу һәм ҡалдыҡтар арифметикаһы |издание=[[Квант (журнал)|Квант]]|номер=5 |йыл 1970 |биттәр=28—33}}</ref>.

== Тарих ==
Сағыштырыу теорияһы барлыҡҡа килеүенең тәүшарты булып [[Диофант Александрийский|Диофанттың]] яҙмаларын тергеҙеү тора. Улар  [[Баше де Мезириак, Клод Гаспар|Баша де Мезириак]] арҡаһында [[1621]] йылда төп нөсхәһендә һәм латин теленә тәржемәләнеп баҫылып сыға. Уларҙы өйрәнеү [[Ферма Пьер|Ферма́ны]] әһәмиәте буйынса ул осорҙо күпкә уҙып киткән асыштарға килтерә. Мәҫәлән,  Френикль де Бессиға {{lang-fr|Bernard Frénicle de Bessy}}<ref>Француз математигы, [[1666]] йылдан Француз фәндәр академияһы ағзаһы.</ref> 1640 йылдың 18 октябрендә яҙған хатында ул, аҙаҡ [[Малая теорема Ферма|Ферманың бәләкәй теоремаһы]] исемен алған [[Малая теорема Ферма|теоремаһын]], иҫбатлауһыҙ әйтеп бирә.    Хәҙерге формулировкала [[Малая теорема Ферма|теорема]]: Әгәр <math>p</math> — [[ябай һан]] һәм <math>a</math> —  <math>p</math>-ға бүленмәгән [[бөтөн һан]] булһа, ул саҡта: <math>a^{p-1}\equiv 1 \pmod p </math> тип раҫлай .
Беренсе булып был теореманы [[Лейбниц Готфрид Вильгельм|Лейбниц]] иҫбатлай, был теореманы ул [[Ферма, Пьер|Ферма́]]ға бәйһеҙ рәүештә  [[1683 йылдан]] алдараҡ аса һәм был турала теүәл иҫбатлауын килтереп [[Бернулли, Иоганн|Бернулли]]ға хәбәр итә. Бынан тыш [[Лейбниц, Готфрид Вильгельм|Лейбниц]] [[Теорема Вильсона|Вильсон теоремаһы]] формулировкаһының прообразын тәҡдим итә.
Һуңғараҡ [[һандар теорияһы]] һәм сағыштырыуҙар теорияһына арналған һорауҙарҙы өйрәнеүҙе [[Эйлер, Леонард|Эйлер]]
дауам итә, ул [[ике яҡлылыҡ квадратик законын взаимности]] индерә һәм [[Ферма теоремаһын]] дөйөмләштерә:

: <math>a^{\varphi(n)}\equiv 1\pmod n, </math>

бында <math>\varphi(n)</math> — [[Эйлер функцияһы]].
[[Гаусс, Карл Фридрих|Гаусс]] [[1795 йыл]]да арифметик теория өҫтөндә эшләй башлай һәм уны нигеҙләүҙең төп инструменты итеп ''сағыштырыу'' төшөнсәһен һәм уның символик тамғаланышын индерә. [[Гаусс, Карл Фридрих|Гауссҡа]] унан алдағы ғалимдарҙың хеҙмәттәре билдәһеҙ була, шуға күрә «''Арифметик эҙләнеүҙәр''» ([[1801 йыл|1801]]) китабының тәүге бүлектәрендә яҙылған хеҙмәттәренең һөҙөмтәһе, дөйөм алғанда, билдәле булған була инде. Шулай ҙа иҫбатлау өсөн ҡулланған методтары яңы, һандар теорияһы үҫеше өсөн бик юғары әһәмиәткә эйә булып сығалар. Был методтарҙы ҡулланып Гаусс, модуле буйынса сағыштырыу ғәмәленә бәйле булған, уға тиклем тупланған бөтә мәғлүмәтте төҙөк теорияға әйләндерә. Был теория тәү башлап ошо китабында яҙылып сыға. Бынан тыш ул беренсе һәм икенсе дәрәжә сағыштырыуҙарҙы, [[квадратичный вычет|квадратик вычетов]] теорияһын һәм уның менән бәйле [[ике яҡлылыҡ квадратик законын]]<ref>{{книга |автор=Вилейтнер Г.|часть=Глава III Теория чисел| ответственный=пер. с нем. под. ред. А. П. Юшкевича|заглавие=История математики от Декарта до середины XIX |место=М. |издательство=Государственное издательство физико-математической литературы |год=1960 |том=|страницы=69—84|страниц=467 |ссылка=http://eqworld.ipmnet.ru/ru/library/mathematics/other.htm}}</ref> тикшерә.

== Билдәләмәләр ==
{{рамка}}
Әгәр ике бөтөн <math>a</math> һәм <math>b</math> һандары <math>m</math> -ға [[бүлеү|бүлгәндә]] бер үк ҡалдыҡтар бирһә, улар  <math>m</math>''' һаны модуле буйынса '''сағыштырырлыҡ''' (йәки '''тигеҙ ҡалдыҡлы''') '''тип аталалар<ref name="Stepanov">{{книга |автор=Степанов С. А.|заглавие=Сравнения |место=М. |издательство=«Знание» |год=1975 |страницы=3—9 |страниц=64 |часть=Глава 1. Основные понятия|ссылка=http://eqworld.ipmnet.ru/ru/library/mathematics/numtheory.htm}}</ref>.
{{/рамка}}
 <math>a</math> һәм <math>b</math> һандарының сағыштырырлыҡ булыуы ('''сағыштырыуҙар''') формулаһы күренешендә яҙыла:

: <math>a\equiv b\pmod m.</math>

<math>m</math> һаны сағыштырыу '''модуле''' тип атала.

<math>a</math> һәм <math>b</math> һандарының <math>m</math> модуле буйынса '''сағыштырырлыҡ булыу''' билдәләмәһе түбәндәге раҫлауҙарҙың теләһә ҡайһыһына [[кәрәкле һәм етерлек шарт|тиң көслө]]:
# <math>a</math> һәм <math>b</math> һандарының айырмаһы <math>m</math>-ға ҡалдыҡһыҙ бүленә;
# <math>a</math> һаны <math>a=b+km</math> күренешендә күрһәтелә ала, бында <math>k</math> —ниндәйҙер [[бөтөн һан]]<ref name="Vinogradov1"/>.

{{Hider|
  title = Иҫбатлау|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
* '''1''' һәм '''2''' [[кәрәкле һәм етерлек шарт|шарттарының кәрәклеге]] ошолай иҫбатлана:
: <math>a\equiv b\pmod m.</math>
Ул саҡта
: <math>a=n_1m + r, 0 \leqslant r< m</math>,
: <math>b=n_2m + r, 0 \leqslant r< m</math> тип уйлағанда,
'''1''' һәм '''2''' үтәлә:
: <math>a-b=(n_1-n_2)m,</math>
: <math>a = n_1m + r=n_1m + r+n_2m-n_2m=b+(n_1-n_2)m=b+kn</math>, бында <math>k=n_1-n_2</math>.
'''1''' һәм '''2''' шарттарының * [[кәрәкле һәм етерлек шарт|етерлек]] шарты:
:<math>a=b+km,</math>
[[необходимое и достаточное условие|Кәрәкле шарттың]] иҫбатлауынан {{math|''b''}} һанын ошолай күрһәтеп була:
:<math>b=n_1m + r, 0 \leqslant r< m</math>.
Ул саҡта
:<math>a=nm + r, 0 \leqslant r< m,</math>, бында <math>n=k+n_1</math>.
Шулай итеп,
: <math>a\equiv b\pmod m.</math>.
Билдәләмәнең '''2''' шартына [[необходимое и достаточное условие|тиң көслө]] булыуы иҫбатланды, ә ул '''1''' шартҡа [[необходимое и достаточное условие|эквивалентлы]].
}}

Мәҫәлән, 32 һәм −10 һандары 7 модуле буйынса сағыштырырлыҡ, сөнки ике һан да 7-гә бүлгәндә 4 ҡалдығы бирә: 
: <math>32 = 7 \cdot 4 + 4; \quad -10 = 7 \cdot (-2) + 4.</math>
Шулай уҡ, 32 һәм −10 һандары 7 модуле буйынса сағыштырырлыҡ, сөнки уларҙың айырмаһы 42 7-гә бүленә, быға өҫтәп түбәндәге күренештә яҙыу урынлы:
: <math>32 = -10 + 6 \cdot 7.</math>

== Модуле буйынса сағыштырырлыҡ булыу үҙсәнлектәре ==
Бирелгән натураль <math>m</math> һаны өсөн <math>m</math> модуле буйынса сағыштырырлыҡ булыу бәйләнеше түбәндәге үҙсәнлектәргә эйә:
* [[Рефлексивность|рефлексивлыҡ]]: теләһә ниндәй бөтөн <math>a</math> һаны өсөн <math>a \equiv a \pmod m.</math> дөрөҫ.
* [[Симметричное отношение|симметриялылыҡ]]: әгәр <math>a \equiv b \pmod m,</math>, ул саҡта <math>b \equiv a \pmod m.</math>
* [[Транзитивность|транзитивлыҡ]]: әгәр <math>a \equiv b \pmod m</math> һәм<math>b \equiv c \pmod m,</math>, ул саҡта <math>a \equiv c \pmod m.</math>

Шулай итеп, <math>m</math> модуле буйынса сағыштырырлыҡ булыу бәйләнеше бөтөн һандар күмәклегендә [[Отношение эквивалентности|эквивалентлылыҡ бәйләнеше]] була<ref>{{книга |автор=Сизый С. В.|заглавие=Лекции по теории чисел |место=М. |издательство=ФИЗМАТЛИТ |год=2008 |ссылка= |страницы=88|страниц=192|isbn=978-5-9221-0741-9|часть=§4. Теория сравнений}}</ref>.

Юғарыла һанап кителгән үҙсәнлектәрҙән тыш, сағыштырыу өсөн түбәндәге раҫлауҙар дөрөҫ:
* теләһә ниндәй ике бөтөн һан 1 модуле буйынса сағыштырырлыҡ.
* әгәр <math>a</math> һәм <math>b</math> һандары <math>m</math> модуле буйынса сағыштырырлыҡ булһа, һәм <math>d</math>  <math>m</math> һанының [[Делитель|бүлеүсеһе]] булһа, ул саҡта <math>a</math> һәм <math>b</math>  <math>d</math> модуле буйынса сағыштырырлыҡ була.
{{Hider|
  title = Иҫбатлау|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
: <math>a\equiv b\pmod m.</math> булһын, ти.
Ошонан сығып,
: <math>a-b=mt.</math>
 <math>d</math>  <math>m</math> һанының [[Делитель|бүлеүсеһе]] булғас, 
:<math>m=cd</math> була.
Тимәк,
: <math> a-b=mt=cdt=qd, (q=ct)</math>
һәм
: <math>a\equiv b\pmod d</math>
билдәләмә буйынса.
}}
* әгәр <math>a</math> һәм <math>b</math> һандары бер нисә модуль <math>{m_1, m_2, ..., m_k}</math> буйынса сағыштырырлыҡ булһа, улар <math>{[m_1, m_2, ..., m_k]}</math> модулдәренең [[Наименьшее общее кратное|иң бәләкәй уртаҡ бүленеүсеһе]]нә тигеҙ булған модуль буйынса сағыштырырлыҡ була.
{{Hider|
  title = Иҫбатлау|
  hidden = 1 |
  title-style = text-align: left; |
  content-style = text-align: left; |
  content =
: <math>a\equiv b\pmod {m_i}, i=1,2,...,k. </math> булһын.
Ошонан сығып,
: <math>a-b=m_it.</math>
<math>a-b</math> айырмаһы һәр <math>m_1</math>-гә бүленгәнлектән, уларҙың [[Наименьшее общее кратное|иң бәләкәй уртаҡ бүленеүсеһенә]] лә бүленә.
}}
: ''Эҙемтә:''
: <math>a</math> һәм <math>b</math> һандары ябай ҡабатлашыусыларға [[каноник тарҡатмаһы]]: <math>m = \prod_{i=1}^d p_i^{\alpha_i},</math> булған <math>m</math> модуле буйынса сағыштырырлыҡ булһын өсөн,  
: <math>a \equiv b \pmod {p_i^{\alpha_i}},\quad i = 1, 2, \dots, d</math>{{sfn|Сагалович|2010|с=25—29}} үтәлеүе кәрәкле һәм етерлек шарт булып тора.

== Сағыштырыу менән ғәмәлдәр ==
Бер үк модуль буйынса сағыштырыу ғәҙәттәге тигеҙлеккә хас күп үҙсәнлектәргә эйә. Мәҫәлән, уларҙы ҡушырға, алырға, ҡабатларға мөмкин: әгәр <math>a_1, a_2, ..., a_n</math> һәм <math>b_1, b_2, ..., b_n</math> һандары парлап <math>m</math> модуле буйынса сағыштырырлыҡ булһалар,уларҙың суммалары ла <math>a_1 + a_2 + ... + a_n</math> һәм <math>b_1 + b_2 + ... + b_n</math>, шулай уҡ ҡабатландыҡтары ла <math>a_1 \cdot a_2 \cdot ... \cdot a_n</math> һәм <math>b_1 \cdot b_2 \cdot ... \cdot b_n</math>  <math>m</math> модуле буйынса сағыштырырлыҡ. Был осраҡта сағыштырыуҙар менән ғәмәлдәрҙе, әгәр уларҙың модулдәре тап килмәһә, башҡарырға ярамай.{{sfn|Сагалович|2010|с=25—29}}.

 Айырым шуны билдәләп китергә кәрәк: сағыштырыуҙың ике өлөшөнә лә бер үк һанды ҡушырға мөмкин; һанды сағыштырыуҙың бер өлөшөнән икенсеһенә тамғаһын үҙгәртеп күсерергә мөмкин.

Әгәр <math>a</math> һәм <math>b</math> һандары <math>m</math> модуле буйынса сағыштырырлыҡ булһа, уларҙың дәрәжәләре <math>a^k</math> һәм <math>b^k</math>  <math>k</math>-ның теләһә ниндәй натураль ҡиммәтендә лә <math>m</math> модуле буйынса сағыштырырлыҡ<ref name="Vinogradov1">{{книга |автор=[[Виноградов, Иван Матвеевич|Виноградов И. М.]] |заглавие=Основы теории чисел |место=М.-Л. |издательство=Гос. изд. технико-теоретической литературы |год=1952 |страницы=41—45 |страниц=180 |ссылка=http://math.ru/lib/book/djvu/vinogradov.djvu}}</ref>.
Сағыштырыуҙың теләһә ҡайһы өлөшөнә модулдең бүленеүсеһенә тигеҙ булған бөтөн һанды ҡушырға мөмкин. Йәғни, әгәр 
<math>a</math> һәм <math>b</math> һандары <math>m</math> модуле буйынса сағыштырырлыҡ булһа, <math>a + t_1</math> һәм <math>b+t_2</math> һандары ла <math>m</math> модуле буйынса сағыштырырлыҡ, (бында <math>t_1</math> һәм <math>t_2</math> — ирекле [[Целое число|бөтөн]] һандар). Шулай уҡ сағыштырыуҙың ике яғын да һәм модулде бер үк һанға ҡабатларға мөмкин. Йәғни, әгәр <math>a</math> һәм <math>b</math> һандары ниндәйҙер [[Целое число|бөтөн]] <math>m</math> һанының модуле буйынса сағыштырырлыҡ булһалар, <math>aq</math> һәм <math>bq</math> һандары ла <math>mq</math> модуле буйынса сағыштырырлыҡ, бында <math>q</math> — [[Целое число|бөтөн]] һан.
Сағыштырыуҙарҙы бер береһенә йәки башҡа һандарға бүлергә ярамай. Миҫал: <math>14 \equiv 20 \pmod 6</math>, әммә, 2-гә ҡыҫҡартып, беҙ хата сағыштырыу табырбыҙ: <math>7 \equiv 10 \pmod 6</math>. Сағыштырыу өсөн ҡыҫҡартыу ҡағиҙәләре ошолай:
* Сағыштырыуҙың ике яғын да модуль менән [[Взаимно простые числа|үҙ-ара ябай]] һанға бүлергә мөмкин: әгәр
: <math> {ad} \equiv {bd} \pmod m</math> һәм '''[[Иң ҙур уртаҡ бүлеүсе|ИҘУБ]]'''<math>{(d,m)=1},</math> булһа, ул саҡта
: <math>a \equiv b \pmod  m</math>.
Әгәр <math>d</math> һаны юғарыла килтерелгән миҫалдағы кеүек модуль менән  [[Взаимно простые числа|үҙ-ара ябай]] булмаһа, <math>d</math> һанына ҡыҫҡартырға ярамай.
* Бер үк ваҡытта сағыштырыуҙың ике яғын да һәм модулде уларҙың уртаҡ бүлеүсеһенә ҡыҫҡартырға мөмкин:
әгәр <math>{ac} \equiv {bc} \pmod {mc}</math>, ул саҡта <math>a \equiv b \pmod  m</math>{{sfn|Сагалович|2010|с=25—29}}.

== Бәйләнешле билдәләмәләр ==

=== Бүлеүҙән ҡалдыҡтар класы ===
<math>a</math> һаны менән <math>m</math> модуле буйынса сағыштырырлыҡ бөтә һандар күмәклеге, '''<math>m</math> модуле буйынса <math>a</math> һанының бүлеүҙән ҡалдыҡтар класы''' тип атала, һәм ғәҙәттә <math>[a]_m</math> йәки <math>\bar a_m</math> тип тамғалана. Шулай итеп, <math>a\equiv b\pmod{m}</math> сағыштырыуы <math>[a]_m=[b]_m</math> бүлеүҙән ҡалдыҡтар класы тигеҙлегенә тиң көслө<ref>{{книга |автор=Бухштаб А. А.|заглавие=Теория чисел |место=М. |издательство=«Просвещение» |год=1966 |ссылка=http://www.e-reading.club/book.php?book=105945 |страницы=77—78|страниц=384|часть=Глава 8. Классы}}</ref>.
Кластағы теләһә ниндәй һан  <math>m</math> модуле буйынса ''бүлеүҙән ҡалдыҡ'' тип атала. 
Асыҡлыҡ өсөн <math>r</math> ― кластың теләһә ниндәй вәкиленең <math>m</math>-ға [[Деление с остатком|бүлеүҙән ҡалдыҡ]]булһын, ул саҡта был кластағы теләһә ниндәй <math>q</math> һанын <math>q = mt + r</math> күренешендә яҙырға мөмкин, бында <math>t</math> —[[Целое число|бөтөн]] һан.  <math>r</math> [[Деление с остатком|ҡалдығына]]  тигеҙ булған бүлеүҙән ҡалдыҡ (вычет)  ''иң бәләкәй тиҫкәре булмаған бүлеүҙән ҡалдыҡ'' тип атала, ә абсолют дәүмәле буйынса иң бәләкәй <math>\rho</math> бүлеүҙән ҡалдыҡ ''абсолют иң бәләкәй бүлеүҙән ҡалдыҡ'' тип атала.  <math>r < \frac {m}{2}\  \rho=r</math> була; кире осраҡта <math>\rho = r - m</math>. Әгәр <math>m</math>-[[йоп һан]] һәм <math>r = \frac{m}{2}</math> булһа, ул саҡта <math>\rho = -\frac{m}{2}</math>{{sfn|Сагалович|2010|с=29—32}}.

<math>m</math> модуле буйынса сағыштырырлыҡ булыу бөтөн һандар күмәклегендә [[отношение эквивалентности|эквивалентлы бәйләнеш]] булғанлыҡтан <math>\mathbb{Z}</math>, <math>m</math> модуле буйынса бүлеүҙән ҡалдыҡтар класы [[отношение эквивалентности|эквивалентлылыҡ класы]] булып тора; уларҙың һаны <math>m</math>-ға тигеҙ.

<math>m</math> модуле буйынса бөтә бүлеүҙән ҡалдыҡтар класы күмәклеге <math>\mathbb{Z}_m</math> йәки <math>\mathbb{Z}/m\mathbb{Z}</math><ref>{{книга |автор=Сизый С. В.|заглавие=Лекции по теории чисел |место=М. |издательство=ФИЗМАТЛИТ |год=2008 |ссылка= |страницы=87—88,91|страниц=192|isbn=978-5-9221-0741-9|часть=§4. Теория сравнений}}</ref> йәки <math>\mathbb{Z}/(m)</math> тип тамғалана<ref>{{книга
|автор        = Лидл Р., Нидеррайтер Г.
|заглавие     = Конечные поля. В 2-х тт
|издание      = 
|место        = М.
|издательство = Мир
|год = 1998
|страниц = 430
|isbn = 5-03-000065-8
|тираж =
|ref = Лидл, Нидеррайтер
|страницы=27 (Пример 1.37)
}}</ref>.

<math>\mathbb{Z}</math> күмәклегендә ҡушыу һәм ҡабатлау ғәмәлдәре  <math>\mathbb{Z}_m</math> күмәклегендәге ярашлы ғәмәлдәрҙе 
[[индуцированная операция|барлыҡҡа килтерә]]:
: <math>[a]_m+[b]_m=[a+b]_m</math>
: <math>[a]_m\cdot [b]_m=[a\cdot b]_m</math>

Был ғәмәлдәргә ҡарата <math>\mathbb{Z}_m</math> күмәклеге сикле [[Кольцо (алгебра)|балдаҡ]] була, ә [[Простое число|ябай]] <math>m</math> һаны өсөн — [[Конечное поле|сикле ялан]]<ref name="Stepanov"/>.

=== Бүлеүҙән ҡалдыҡтар системаһы ===
Бүлеүҙән ҡалдыҡтар системаһы сикле һандар йыйылмаһы өҫтөндә, унан ситкә сыҡмайынса, арифметик ғәмәлдәр башҡарырға мөмкинлек бирә.
<!-- бывшая статья [[Полная система вычетов]] ― тема не имеет значения в отрыве от. --Incnis Mrsi -->
<math>m</math> модуле буйынса '''бүлеүҙән ҡалдыҡтарҙың тулы системаһы'''― <math>m</math> модуле буйынса сағыштырырлыҡ булмаған <math>m</math> бөтөн һандың теләһә ниндәй йыйылмаһы.
Ғәҙәттә <math>m</math> модуле буйынса бүлеүҙән ҡалдыҡтарҙың тулы системаһы сифатында ике күмәклектең береһе алына:
:[[таҡ]] <math>m</math> осрағында
* '''иң бәләкәй тиҫкәре булмаған бүлеүҙән ҡалдыҡтар''', йәғни
:: <math>0, 1, ... , m-1</math> һандары,
* йәки :: <math>0,\pm1,\pm2,...,\pm\frac{m-1}{2}</math> һандарынан торған '''абсолют иң бәләкәй бүлеүҙән ҡалдыҡтар''';
:[[йоп]] <math>m</math> осрағында
:: <math>0,\pm1,\pm2,...,\pm(\frac{m}{2}-1),\frac{m}{2}</math> һандары.

<math>m</math> менән [[взаимная простота|үҙ-ара ябай булған]],  <math>m</math> модуле буйынса парлап сағыштырырлыҡ булмаған һандарҙың иң ҙур йыйылмаһы, <math>m</math> модуле буйынса '''[[Приведённая система вычетов|килтерелгән бүлеүҙән ҡалдыҡтар системаһы]]''' тип атала. Һәр <math>m</math> модуле буйынса килтерелгән бүлеүҙән ҡалдыҡтар системаһының <math>\varphi(m)</math> элементы бар, бында <math>\varphi(\cdot)</math> — [[Эйлер функцияһы]]{{sfn|Сагалович|2010|с=29—32}}.

Мәҫәлән, <math>m=42</math> һаны өсөн ''бүлеүҙән ҡалдыҡтарҙың тулы системаһы'' түбәндәге һандар менән бирелә:  <math>0,1,2,3,...,21,22,23,...,39,40,41 </math>, ә ''килтерелгән бүлеүҙән ҡалдыҡтар системаһы'' — <math>1,5,11,13,17,19,23,25,29,31,37,41</math> һандары.

=== Күпбыуындар күмәклегендә сағыштырыуҙар ===
<math>K</math> [[Поле (алгебра)|өлкә]]һендә <math>K[x]</math> [[күпбыуындар күмәклеген]]  ҡарайыҡ. Был күмәклеккә ингән ике  <math>g_1</math> һәм <math>g_2</math> [[күпбыуын]]дары, әгәр уларҙың айырмаһы <math>g_1-g_2</math>  <math>f</math> күпбыуынына ҡалдыҡһыҙ  [[Деление с остатком|бүленһә]], <math>f</math> [[күпбыуыны]] буйынса сағыштырырлыҡ тип аталалар.Сағыштырыу ошолай тамғалана:
: <math>g_1\equiv g_2\pmod f.</math>
Бөтөн һандар күмәклегендәге кеүек, был сағыштырыуҙарҙы ҡушырға, алырға, ҡабатларға мөмкин<ref>{{книга |автор=Фадеев Д. К.|заглавие=Лекции по алгебре|издание= |место=М.|издательство=«Наука» |год=1984 |страницы=197—198 |страниц=416 |часть=Глава VII. Сравнение в кольце полиномов и расширения полей|ссылка=http://book.isito.kg/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0/%D0%94.%D0%9A.%D0%A4%D0%B0%D0%B4%D0%B4%D0%B5%D0%B5%D0%B2%20-%20%D0%9B%D0%B5%D0%BA%D1%86%D0%B8%D0%B8%20%D0%BF%D0%BE%20%D0%B0%D0%BB%D0%B3%D0%B5%D0%B1%D1%80%D0%B5.%20416%20%D1%81%D1%82%D1%80.%20%D0%9C.,%20%D0%9D%D0%B0%D1%83%D0%BA%D0%B0,%201984.pdf}}</ref>.

== Сағыштырыуҙарҙы сығарыу ==

=== Беренсе дәрәжә сағыштырыуҙар ===
[[теория чисел|Һандар теорияһында]], [[криптография]]ла һәм фәндең башҡа өлкәләрендә йыш ҡына : <math>ax \equiv b\pmod {m}.</math> күренешендәге беренсе дәрәжә сағыштырыуҙарҙың сығарылышын табыу мәсьәләһе тыуа.
Был сағыштырыуҙарҙы сығарыу  <math>d = </math> [[Иң ҙур уртаҡ бүлеүсе|'''ИҘУБ''']] <math>(a,m)</math> табыуҙан башлана. Ике осраҡ булыуы мөмкин:
* Әгәр <math>b</math> <math>d</math>-ға бүленмәһә, сағыштырыуҙың сығарылышы юҡ.
* Әгәр <math>b</math> <math>d</math>-ға бүленһә, сағыштырыуҙың <math>\frac{m}{d}</math> модуле буйынса берҙән-бер сығарылышы бар, йәки, шуны уҡ аңлата, <math>m</math> модуле буйынса  <math>d</math> сығарылышы бар. Был осраҡта бирелгән сағыштырыуҙы <math>d</math>-ға ҡыҫҡартыу һөҙөмтәһендә :: <math>a_1 x \equiv b_1\pmod {m_1}</math> сағыштырыуы табыла, бында 
 <math>a_1 = \frac{a}{d}</math>, <math>b_1 = \frac{b}{d}</math> и <math>m_1 = \frac{m}{d}</math> [[Целое число|бөтөн һандар]]булып торалар, шуның менән бергә <math>a_1</math> һәм <math>m_1</math> үҙ-ара ябай. Шуға күрә <math>a_1</math> һанын <math>m_1</math> модуле буйынса үҙгәртергә мөмкин, йәғни <math>c\cdot a_1\equiv 1\pmod{m_1}</math> үтәлерлек <math>c</math> һанын табырға (икенсе төрлө, <math>c \equiv a_1^{-1}\pmod{m_1}</math>). Сығарылышты табыу өсөн килеп сыҡҡан сағыштырыуҙы <math>c</math> -ға ҡабатларға кәрәк:
:: <math>x \equiv c a_1 x\equiv c b_1\equiv a_1^{-1} b_1\pmod {m_1}.</math>
 <math>c</math>-ның ҡиммәтен иҫәпләүҙе практикала төрлө ысул менән башҡарырға мөмкин: [[Теорема Эйлера (теория чисел)|Эйлер теоремаһы]], [[алгоритм Евклида|Евклид алгоритмы]], [[цепная дробь|кәсерҙәр сылбыры]] теорияһы (см. [[Непрерывная дробь#Решение сравнений первой степени|алгоритм]]) һ. б. ярҙамында . Айырым осраҡта, [[Теорема Эйлера (теория чисел)|Эйлер теоремаһы]]  <math>c</math>-ның ҡиммәтен: <math>c \equiv a_1^{-1}\equiv a_1^{\varphi(m_1)-1}\pmod {m_1}</math> күренешендә яҙырға мөмкинлек бирә<ref>{{книга |автор=Сизый С. В.|заглавие=Лекции по теории чисел |место=М. |издательство=ФИЗМАТЛИТ |год=2008 |ссылка= |страницы=105—109|страниц=192|isbn=978-5-9221-0741-9|часть=§4. Теория сравнений}}</ref>.

==== Миҫалдар ====
; Миҫал 1. 
: <math>4x\equiv 26\pmod {22}</math> сағыштырыуы өсөн <math>d=2</math>, шуға күрә 22 модуле буйынса сағыштырыуҙың ике сығарылышы бар. 26-ны уның менән 22 модуле буйынса сағыштырырлыҡ 4-кә үҙгәртәбеҙ һәм 3 һанды ла 2-гә ҡыҫҡартабыҙ:
: <math>2x \equiv 2\pmod {11}</math>
2 һаны 11 модуле менән үҙ-ара ябай булғас, уны 11 модуле буйынса үҙгәртергә мөмкин, һәм табабыҙ: <math>2^{-1}\equiv 6\pmod{11}</math>.
Сағыштырыуҙы 6-ға ҡабатлап, 11 модуле буйынса сығарылыш табабыҙ:
: <math>x\equiv 1\pmod {11}</math>. Был 22 модуле буйынса ике сығарылыштың йыйылмаһына эквивалент:
:<math>x\equiv 1\pmod {22}</math> и <math>x\equiv 12\pmod {22}</math>.

; Миҫал 2. 
: <math>100 x \equiv 41\pmod {65537}.</math> сағыштырыуы бирелгән. <math>65537</math>  модуле — ябай һан.
Сығарыуҙың беренсе ысулы - [[Соотношение Безу|Безу нисбәте]] менән файҙаланыу. [[Алгоритм Евклида|Евклид алгоритмы]] йәки Безу нисбәте тураһындағы мәҡәләлә килтерелгән программа ярҙамында <math>100</math> һәм <math>65537</math> һандары өсөн был нисбәттәр түбәндәге күренештә булыуын табабыҙ:
: <math>17695 \cdot 100 + (-27) \cdot 65537 = 1,</math> йәки <math>17695 \cdot 100 \equiv 1 \pmod {65537}</math>
Был сағыштырыуҙарҙың ике яғын да 41-гә ҡабатлап табабыҙ:
: <math>100 \cdot 725495 \equiv 41 \pmod {65537}</math>
Бынан <math>725495</math> һаны бирелгән сағыштырыуҙың сығарылышы булыуы килеп сыға. Был һанды уның менән сағыштырырлыҡ булған  <math>4588</math> һанына алмаштырыу уңайлыраҡ (<math>725495</math>-те <math>65537</math>-гә бүлеүҙән ҡалдыҡ). Яуап: <math>x \equiv 4588 \pmod {65537}.</math>

Сығарыуҙың икенсе ысулы ябайыраҡ та һәм тиҙерәк тә, Безу нисбәтен төҙөп тороу кәрәкмәй, ләкин Евклид алгоритмына эквивалентлы.

 1 аҙым. Модулде x-тың коэффициентына ҡалдыҡлы бүләбеҙ: <math>65537=100 \cdot 655+37</math>. Бирелгән сағыштырыуҙың ике яғын да  <math>655</math> бүлендегенә ҡабатлайбыҙ һәм <math>37x</math> -ты ҡушабыҙ. Табабыҙ: <math>65537x \equiv 26855+37x \pmod {65537}</math>, әммә һул яғы <math>65537</math>-гә бүленә, йәғни нуль менән сағыштырырлыҡ, шунан сығып:
: <math>37x \equiv -26855 \pmod {65537}</math>
Беҙ <math>x</math> алдында 100 урынына 37 коэффициентын таптыҡ. Артабанғы һәр аҙымда ошоға оҡшаш рәүештә, берҙе тапҡанға тиклем, кәметәбеҙ.

 2 аҙым. Оҡшаш рәүештә x-тың яңы коэффициентына бүләбеҙ: <math>65537=37 \cdot 1771+10</math>. Алдағы аҙымда килеп сыҡҡан сағыштырыуҙың ике яғын да <math>1771</math> бүлендегенә ҡабатлайбыҙ һәм <math>10x</math>-ты ҡушабыҙ; һул яғын тағы ла нулгә алмаштырып, табабыҙ:
: <math>10x \equiv 47560205 \pmod {65537}</math>
<math>47560205</math>-те, уны <math>65537,</math>-гә бүлгәндәге <math>45880</math> ҡалдығына алмаштырабыҙ:
: <math>10x \equiv 45880 \pmod {65537}</math>
Артабан ошоға оҡшаш тағы 5 аҙым яһарға булыр ине, ләкин сағыштырыуҙың ике яғын да 10-ға бүлергә лә, шунда уҡ яуапты табыу ябайыраҡ : <math>x \equiv 4588 \pmod {65537}.</math>

=== Икенсе дәрәжә сағыштырыуҙар ===
Ябай {{math|''m''}} модуле буйынса икенсе дәрәжә сағыштырыуҙар түбәндәге дөйөм күренештә:
: <math>c_0x^2+c_1x+c \equiv 0\pmod {m}.</math>
Был аңлатманы : <math>(x+b)^2\equiv a\pmod {m}.</math> күренешенә килтерергә була, ә  <math>z = x+ b</math> менән алмаштырғанда тағы ла ябайлаша:
: <math>(z)^2\equiv a\pmod {m}.</math>.
Был сағыштырыуҙы сығарыу ([[квадратичный закон взаимности|уртаҡлыҡтың квадратик законы]] ярҙамында) был һандың [[квадратичный вычет|квадратик бүлеүҙән ҡалдыҡ]] буламы икәнен тикшереүгә һәм артабан бирелгән модуль буйынса [[квадратный корень|квадрат тамырҙы]] табыуға ҡайтып ҡала<ref>{{книга |автор=Бухштаб А. А.|заглавие=Теория чисел |место=М. |издательство=«Просвещение» |год=1966 |ссылка=http://www.e-reading.club/book.php?book=105945 |страницы=172—201|страниц=384|часть=Глава 21. Сравнения 2-й степени по простому модулю, Глава 22. Сравнения второй степени по составному модулю}}</ref>. Квадратик бүлеүҙән ҡалдыҡтан квадрат тамырҙы иҫәпләү өсөн ихтималлыҡ [[Берлекэмп методы]] бар.

=== Сағыштырыуҙар системаһы ===
{{main|Ҡалдыҡтар тураһында Ҡытай теоремаһы}}
[[Ҡалдыҡтар тураһында Ҡытай теоремаһы]] раҫлауынса, парлы рәүештә [[взаимно простые числа|үҙ-ара ябай]]  <math>m_1, m_2, \ldots, m_n</math> модулдәре менән сағыштырыуҙар системаһының:
: <math>\begin{cases}
x \equiv a_1 \pmod {m_1}\\
x \equiv a_2 \pmod {m_2}\\
  \ldots \\
x \equiv a_n \pmod {m_n}
\end{cases}</math>
һәр саҡ сығарылышы бар һәм ул <math>m_1 \cdot m_2 \cdots m_n</math> модуле буйынса берҙән-бер.
Икенсе һүҙ менән әйткәндә, ҡалдыҡтар тураһында Ҡытай теоремаһы, бер нисә үҙ-ара ябай һандарҙың ҡабатландығы модуле буйынса бүлеүҙән ҡалдыҡтар күмәклеге - ҡабатлашыусыларға ярашлы бүлеүҙән ҡалдыҡтар күмәклектәренең [[прямое произведение|ҡабатландығы]] була, тип раҫлай

== Ҡулланыу ==
Сағыштырыуҙар теорияһының методтары [[Теория чисел|һандар теорияһында]], [[Теория групп|төркөмдәр теорияһында]], [[Теория колец|күмәклектәр теорияһында]], [[Теория узлов|төйөндәр теорияһында]], [[Общая алгебра|дөйөм алгебрала]], [[криптография]]ла, [[информатика]]ла, [[химия]]ла һәм башҡа өлкәләрҙә ҡулланыла.

Мәҫәлән, сағыштырыуҙар идентификаторҙарҙа ҡулланылған контроль суммаларҙы иҫәпләгәндә йыш ҡулланыла. Шулай, IBAN (ISO 13616)|банк иҫәбенең халыҡ-ара номерын индергәндә хатаны асыҡлау өсөн 97 модуле буйынса сағыштырыу ҡулланыла<ref>{{книга |автор=Harald Niederreiter, Arne Winterhof|заглавие=Applied Number Theory |место= |издательство=«Springer» |год=2015|страницы=369 |страниц=442 |isbn=978-3-319-22321-6}}</ref>.
Криптографияла сағыштырыуҙарҙы, [[RSA|RSA алгоритмы]] йәки [[Протокол Диффи — Хеллмана|Диффи — Хеллман протоколы]] ҡулланған [[Криптосистема с открытым ключом|асыҡ асҡыслы системаларҙа]] осратырға мөмкин. Шулай уҡ, модулле арифметика, аҙаҡ [[Эллиптическая кривая|эллиптик кәкере һыҙыҡтары]] төҙөләсәк [[Конечное поле|сикле күмәклектәрҙе]] тәьмин итә һәм симметрик асҡыслы төрлө протоколдарҙа ҡулланыла ([[Advanced Encryption Standard|AES]], [[IDEA]])<ref>{{книга |автор=Коблиц Н.|ответственный=пер. с англ. М. А. Михайловой и В. Е. Тараканова под ред. А. М. Зубкова| заглавие=Курс теории чисел и криптографии|издание=|место=М.|издательство=Научное изд-во ТВП|год=2001 |страницы=96, 105—109, 200—209|страниц=262|isbn=5-85484-012-X|ссылка=}}</ref>.

Химияла [[Регистрационный номер CAS|CAS регистрация номерында]] һуңғы цифр - номерҙың һуңғы цифрының 1-гә ҡабатландығын, уңдан икенсе цифрҙың 2-гә ҡабатландығын, өсөнсө цифрҙың 3-кә ҡабатландығын һ.б. һулдан беренсе цифрға тиклем ҡушыу юлы менән табылған һанды 10-ға бүлеүҙән килеп сыҡҡан ҡалдыҡ [[Контрольная сумма|контроль сумманың]] ҡиммәте булып тора<ref>{{cite web |url=https://www.cas.org/content/chemical-substances/checkdig |title=Check Digit Verification of CAS Registry Numbers |author= |date= |work= |publisher= |accessdate= |lang=en}}</ref>

== Шулай уҡ ҡарағыҙ ==
* [[2 модуле буйынса ҡушыу]]
* [[Модуле буйынса дәрәжәгә күтәреү]]
* [[Модуле буйынса һандың күрһәткесе]]
* [[Модуле буйынса тиҙ дәрәжәгә күтәреү алгоритмы]]

== Иҫкәрмәләр ==
{{примечания|2}}

== Әҙәбиәт ==
* {{книга |автор=[[Вейль, Андре|Вейль А.]] |заглавие=Һандар теорияһы нигеҙҙәре |место=М. |издательство=Мир |год=1972|ссылка=http://eqworld.ipmnet.ru/ru/library/mathematics/numtheory.htm}}
* {{статья |автор=[[Виленкин, Наум Яковлевич|Виленкин Н. Я.]] |ссылка=http://kvant.mccme.ru/1978/10/sravneniya_i_klassy_vychetov.htm |заглавие=Сравнения и классы вычетов |издание=[[Квант (журнал)|Квант]] |номер=10 |год=1978 |страницы=4—8}}
* {{книга |автор=[[Виноградов, Иван Матвеевич|Виноградов И. М.]] |заглавие=Һандар теорияһы нигеҙҙәре |место=М.-Л. |издательство=Гос. изд. технико-теоретической литературы |год=1952 |страниц=180 |ссылка=http://math.ru/lib/book/djvu/vinogradov.djvu}}
* {{книга |автор=Сизый С. В.|заглавие=Һандар теорияһы буйынса лекциялар |место=Екатеринбург |издательство=Уральский государственный университет им. А. М. Горького |год=1999 |ссылка=http://virlib.eunnet.net/books/numbers/ |часть=§4. Теория сравнений}}
* {{книга |автор=Бухштаб А. А.|заглавие=Һандар теорияһы |место=М. |издательство=«Просвещение» |год=1966 |ссылка=http://www.e-reading.club/book.php?book=105945  |страницы=|страниц=384|часть=}}
* {{source|Q22328165|ref=Сагалович|ref-year=2010}} <!-- Введение в алгебраические коды -->
* {{книга |автор=Коблиц Н.|ответственный=пер. с англ. М. А. Михайловой и В. Е. Тараканова,под ред. А. М. Зубкова| заглавие=Курс теории чисел и криптографии|издание=|место=М.|издательство=Научное изд-во ТВП|год=2001 |страницы= |страниц=254||isbn=5-85484-012-X|ссылка=}}
* {{cite web|url=http://www.computer-museum.ru/histussr/sokconf0.htm|title=Материалы международной научной конференции “Модулярная арифметика”|date=2005|publisher=Виртуальный компьютерный музей|accessdate=2010-07-31}}

{{Добротная статья|Математика}}

[[Категория:Математик бәйләнештәр]]
[[Категория:Модуль арифметикаһы| ]]
[[Категория:Дискрет математика]]
[[Категория:Бүлеү һәм ҡалдыҡтар]]