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

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

Мо́дулле арифме́тика, йыш ҡына модуля́р арифметика тип атала^[1]^[2] математикала, информатикала һәм криптографияла киң ҡулланыла^[3].

Тарих

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

a^{\varphi (n)}\equiv 1{\pmod {n}},

бында $\varphi (n)$ — Эйлер функцияһы. Гаусс 1795 йылда арифметик теория өҫтөндә эшләй башлай һәм уны нигеҙләүҙең төп инструменты итеп сағыштырыу төшөнсәһен һәм уның символик тамғаланышын индерә. Гауссҡа унан алдағы ғалимдарҙың хеҙмәттәре билдәһеҙ була, шуға күрә «Арифметик эҙләнеүҙәр» (1801) китабының тәүге бүлектәрендә яҙылған хеҙмәттәренең һөҙөмтәһе, дөйөм алғанда, билдәле булған була инде. Шулай ҙа иҫбатлау өсөн ҡулланған методтары яңы, һандар теорияһы үҫеше өсөн бик юғары әһәмиәткә эйә булып сығалар. Был методтарҙы ҡулланып Гаусс, модуле буйынса сағыштырыу ғәмәленә бәйле булған, уға тиклем тупланған бөтә мәғлүмәтте төҙөк теорияға әйләндерә. Был теория тәү башлап ошо китабында яҙылып сыға. Бынан тыш ул беренсе һәм икенсе дәрәжә сағыштырыуҙарҙы, квадратик вычетов теорияһын һәм уның менән бәйле ике яҡлылыҡ квадратик законын^[5] тикшерә.

Билдәләмәләр

Әгәр ике бөтөн $a$ һәм $b$ һандары $m$ -ға бүлгәндә бер үк ҡалдыҡтар бирһә, улар $m$ һаны модуле буйынса сағыштырырлыҡ (йәки тигеҙ ҡалдыҡлы) тип аталалар^[6].

 $a$  һәм  $b$  һандарының сағыштырырлыҡ булыуы (сағыштырыуҙар) формулаһы күренешендә яҙыла:

a\equiv b{\pmod {m}}.

$m$ һаны сағыштырыу модуле тип атала.

$a$ һәм $b$ һандарының $m$ модуле буйынса сағыштырырлыҡ булыу билдәләмәһе түбәндәге раҫлауҙарҙың теләһә ҡайһыһына тиң көслө:

$a$ һәм $b$ һандарының айырмаһы $m$ -ға ҡалдыҡһыҙ бүленә;
$a$ һаны $a=b+km$ күренешендә күрһәтелә ала, бында $k$ —ниндәйҙер бөтөн һан^[7].

Иҫбатлау

1 һәм 2 шарттарының кәрәклеге ошолай иҫбатлана:

a\equiv b{\pmod {m}}.

Ул саҡта

a=n_{1}m+r,0\leqslant r<m

,

b=n_{2}m+r,0\leqslant r<m

тип уйлағанда,

1 һәм 2 үтәлә:

a-b=(n_{1}-n_{2})m,

a=n_{1}m+r=n_{1}m+r+n_{2}m-n_{2}m=b+(n_{1}-n_{2})m=b+kn

, бында

k=n_{1}-n_{2}

.

1 һәм 2 шарттарының * етерлек шарты:

a=b+km,

Кәрәкле шарттың иҫбатлауынан b һанын ошолай күрһәтеп була:

b=n_{1}m+r,0\leqslant r<m

.

Ул саҡта

a=nm+r,0\leqslant r<m,

, бында

n=k+n_{1}

.

Шулай итеп,

a\equiv b{\pmod {m}}.

.

Билдәләмәнең 2 шартына тиң көслө булыуы иҫбатланды, ә ул 1 шартҡа эквивалентлы.

Мәҫәлән, 32 һәм −10 һандары 7 модуле буйынса сағыштырырлыҡ, сөнки ике һан да 7-гә бүлгәндә 4 ҡалдығы бирә:

32=7\cdot 4+4;\quad -10=7\cdot (-2)+4.

Шулай уҡ, 32 һәм −10 һандары 7 модуле буйынса сағыштырырлыҡ, сөнки уларҙың айырмаһы 42 7-гә бүленә, быға өҫтәп түбәндәге күренештә яҙыу урынлы:

32=-10+6\cdot 7.

Модуле буйынса сағыштырырлыҡ булыу үҙсәнлектәре

Бирелгән натураль $m$ һаны өсөн $m$ модуле буйынса сағыштырырлыҡ булыу бәйләнеше түбәндәге үҙсәнлектәргә эйә:

рефлексивлыҡ: теләһә ниндәй бөтөн $a$ һаны өсөн $a\equiv a{\pmod {m}}.$ дөрөҫ.
симметриялылыҡ: әгәр $a\equiv b{\pmod {m}},$ , ул саҡта $b\equiv a{\pmod {m}}.$
транзитивлыҡ: әгәр $a\equiv b{\pmod {m}}$ һәм $b\equiv c{\pmod {m}},$ , ул саҡта $a\equiv c{\pmod {m}}.$

Шулай итеп, $m$ модуле буйынса сағыштырырлыҡ булыу бәйләнеше бөтөн һандар күмәклегендә эквивалентлылыҡ бәйләнеше була^[8].

Юғарыла һанап кителгән үҙсәнлектәрҙән тыш, сағыштырыу өсөн түбәндәге раҫлауҙар дөрөҫ:

теләһә ниндәй ике бөтөн һан 1 модуле буйынса сағыштырырлыҡ.
әгәр $a$ һәм $b$ һандары $m$ модуле буйынса сағыштырырлыҡ булһа, һәм $d$ $m$ һанының бүлеүсеһе булһа, ул саҡта $a$ һәм $b$ $d$ модуле буйынса сағыштырырлыҡ була.

Иҫбатлау

a\equiv b{\pmod {m}}.

булһын, ти.

Ошонан сығып,

a-b=mt.

 $d$    $m$  һанының бүлеүсеһе булғас,

m=cd

була.

Тимәк,

a-b=mt=cdt=qd,(q=ct)

һәм

a\equiv b{\pmod {d}}

билдәләмә буйынса.

әгәр $a$ һәм $b$ һандары бер нисә модуль ${m_{1},m_{2},...,m_{k}}$ буйынса сағыштырырлыҡ булһа, улар ${[m_{1},m_{2},...,m_{k}]}$ модулдәренең иң бәләкәй уртаҡ бүленеүсеһенә тигеҙ булған модуль буйынса сағыштырырлыҡ була.

Иҫбатлау

a\equiv b{\pmod {m_{i}}},i=1,2,...,k.

булһын.

Ошонан сығып,

a-b=m_{i}t.

$a-b$ айырмаһы һәр $m_{1}$ -гә бүленгәнлектән, уларҙың иң бәләкәй уртаҡ бүленеүсеһенә лә бүленә.

Эҙемтә:

a

һәм

b

һандары ябай ҡабатлашыусыларға каноник тарҡатмаһы:

m=\prod _{i=1}^{d}p_{i}^{\alpha _{i}},

булған

m

модуле буйынса сағыштырырлыҡ булһын өсөн,

a\equiv b{\pmod {p_{i}^{\alpha _{i}}}},\quad i=1,2,\dots ,d

^[9] үтәлеүе кәрәкле һәм етерлек шарт булып тора.

Сағыштырыу менән ғәмәлдәр

Бер үк модуль буйынса сағыштырыу ғәҙәттәге тигеҙлеккә хас күп үҙсәнлектәргә эйә. Мәҫәлән, уларҙы ҡушырға, алырға, ҡабатларға мөмкин: әгәр $a_{1},a_{2},...,a_{n}$ һәм $b_{1},b_{2},...,b_{n}$ һандары парлап $m$ модуле буйынса сағыштырырлыҡ булһалар,уларҙың суммалары ла $a_{1}+a_{2}+...+a_{n}$ һәм $b_{1}+b_{2}+...+b_{n}$ , шулай уҡ ҡабатландыҡтары ла $a_{1}\cdot a_{2}\cdot ...\cdot a_{n}$ һәм $b_{1}\cdot b_{2}\cdot ...\cdot b_{n}$ $m$ модуле буйынса сағыштырырлыҡ. Был осраҡта сағыштырыуҙар менән ғәмәлдәрҙе, әгәр уларҙың модулдәре тап килмәһә, башҡарырға ярамай.^[9].

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

Әгәр $a$ һәм $b$ һандары $m$ модуле буйынса сағыштырырлыҡ булһа, уларҙың дәрәжәләре $a^{k}$ һәм $b^{k}$ $k$ -ның теләһә ниндәй натураль ҡиммәтендә лә $m$ модуле буйынса сағыштырырлыҡ^[7]. Сағыштырыуҙың теләһә ҡайһы өлөшөнә модулдең бүленеүсеһенә тигеҙ булған бөтөн һанды ҡушырға мөмкин. Йәғни, әгәр $a$ һәм $b$ һандары $m$ модуле буйынса сағыштырырлыҡ булһа, $a+t_{1}$ һәм $b+t_{2}$ һандары ла $m$ модуле буйынса сағыштырырлыҡ, (бында $t_{1}$ һәм $t_{2}$ — ирекле бөтөн һандар). Шулай уҡ сағыштырыуҙың ике яғын да һәм модулде бер үк һанға ҡабатларға мөмкин. Йәғни, әгәр $a$ һәм $b$ һандары ниндәйҙер бөтөн $m$ һанының модуле буйынса сағыштырырлыҡ булһалар, $aq$ һәм $bq$ һандары ла $mq$ модуле буйынса сағыштырырлыҡ, бында $q$ — бөтөн һан. Сағыштырыуҙарҙы бер береһенә йәки башҡа һандарға бүлергә ярамай. Миҫал: $14\equiv 20{\pmod {6}}$ , әммә, 2-гә ҡыҫҡартып, беҙ хата сағыштырыу табырбыҙ: $7\equiv 10{\pmod {6}}$ . Сағыштырыу өсөн ҡыҫҡартыу ҡағиҙәләре ошолай:

Сағыштырыуҙың ике яғын да модуль менән үҙ-ара ябай һанға бүлергә мөмкин: әгәр

{ad}\equiv {bd}{\pmod {m}}

һәм ИҘУБ

{(d,m)=1},

булһа, ул саҡта

a\equiv b{\pmod {m}}

.

Әгәр $d$ һаны юғарыла килтерелгән миҫалдағы кеүек модуль менән үҙ-ара ябай булмаһа, $d$ һанына ҡыҫҡартырға ярамай.

Бер үк ваҡытта сағыштырыуҙың ике яғын да һәм модулде уларҙың уртаҡ бүлеүсеһенә ҡыҫҡартырға мөмкин:

әгәр ${ac}\equiv {bc}{\pmod {mc}}$ , ул саҡта $a\equiv b{\pmod {m}}$ ^[9].

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

Бүлеүҙән ҡалдыҡтар класы

$a$ һаны менән $m$ модуле буйынса сағыштырырлыҡ бөтә һандар күмәклеге, $m$ модуле буйынса $a$ һанының бүлеүҙән ҡалдыҡтар класы тип атала, һәм ғәҙәттә $[a]_{m}$ йәки ${\bar {a}}_{m}$ тип тамғалана. Шулай итеп, $a\equiv b{\pmod {m}}$ сағыштырыуы $[a]_{m}=[b]_{m}$ бүлеүҙән ҡалдыҡтар класы тигеҙлегенә тиң көслө^[10]. Кластағы теләһә ниндәй һан $m$ модуле буйынса бүлеүҙән ҡалдыҡ тип атала. Асыҡлыҡ өсөн $r$ ― кластың теләһә ниндәй вәкиленең $m$ -ға бүлеүҙән ҡалдыҡбулһын, ул саҡта был кластағы теләһә ниндәй $q$ һанын $q=mt+r$ күренешендә яҙырға мөмкин, бында $t$ —бөтөн һан. $r$ ҡалдығына тигеҙ булған бүлеүҙән ҡалдыҡ (вычет) иң бәләкәй тиҫкәре булмаған бүлеүҙән ҡалдыҡ тип атала, ә абсолют дәүмәле буйынса иң бәләкәй $\rho$ бүлеүҙән ҡалдыҡ абсолют иң бәләкәй бүлеүҙән ҡалдыҡ тип атала. $r<{\frac {m}{2}}\ \rho =r$ була; кире осраҡта $\rho =r-m$ . Әгәр $m$ -йоп һан һәм $r={\frac {m}{2}}$ булһа, ул саҡта $\rho =-{\frac {m}{2}}$ ^[11].

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

$m$ модуле буйынса бөтә бүлеүҙән ҡалдыҡтар класы күмәклеге $\mathbb {Z} _{m}$ йәки $\mathbb {Z} /m\mathbb {Z}$ ^[12] йәки $\mathbb {Z} /(m)$ тип тамғалана^[13].

$\mathbb {Z}$ күмәклегендә ҡушыу һәм ҡабатлау ғәмәлдәре $\mathbb {Z} _{m}$ күмәклегендәге ярашлы ғәмәлдәрҙе барлыҡҡа килтерә:

[a]_{m}+[b]_{m}=[a+b]_{m}

[a]_{m}\cdot [b]_{m}=[a\cdot b]_{m}

Был ғәмәлдәргә ҡарата $\mathbb {Z} _{m}$ күмәклеге сикле балдаҡ була, ә ябай $m$ һаны өсөн — сикле ялан^[6].

Бүлеүҙән ҡалдыҡтар системаһы

Бүлеүҙән ҡалдыҡтар системаһы сикле һандар йыйылмаһы өҫтөндә, унан ситкә сыҡмайынса, арифметик ғәмәлдәр башҡарырға мөмкинлек бирә. $m$ модуле буйынса бүлеүҙән ҡалдыҡтарҙың тулы системаһы― $m$ модуле буйынса сағыштырырлыҡ булмаған $m$ бөтөн һандың теләһә ниндәй йыйылмаһы. Ғәҙәттә $m$ модуле буйынса бүлеүҙән ҡалдыҡтарҙың тулы системаһы сифатында ике күмәклектең береһе алына:

таҡ

m

осрағында

иң бәләкәй тиҫкәре булмаған бүлеүҙән ҡалдыҡтар, йәғни

0,1,...,m-1

һандары,

йәки :: $0,\pm 1,\pm 2,...,\pm {\frac {m-1}{2}}$ һандарынан торған абсолют иң бәләкәй бүлеүҙән ҡалдыҡтар;

йоп

m

осрағында

0,\pm 1,\pm 2,...,\pm ({\frac {m}{2}}-1),{\frac {m}{2}}

һандары.

$m$ менән үҙ-ара ябай булған, $m$ модуле буйынса парлап сағыштырырлыҡ булмаған һандарҙың иң ҙур йыйылмаһы, $m$ модуле буйынса килтерелгән бүлеүҙән ҡалдыҡтар системаһы тип атала. Һәр $m$ модуле буйынса килтерелгән бүлеүҙән ҡалдыҡтар системаһының $\varphi (m)$ элементы бар, бында $\varphi (\cdot )$ — Эйлер функцияһы^[11].

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

Күпбыуындар күмәклегендә сағыштырыуҙар

$K$ өлкәһендә $K[x]$ күпбыуындар күмәклеген ҡарайыҡ. Был күмәклеккә ингән ике $g_{1}$ һәм $g_{2}$ күпбыуындары, әгәр уларҙың айырмаһы $g_{1}-g_{2}$ $f$ күпбыуынына ҡалдыҡһыҙ бүленһә, $f$ күпбыуыны буйынса сағыштырырлыҡ тип аталалар.Сағыштырыу ошолай тамғалана:

g_{1}\equiv g_{2}{\pmod {f}}.

Бөтөн һандар күмәклегендәге кеүек, был сағыштырыуҙарҙы ҡушырға, алырға, ҡабатларға мөмкин^[14].

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

Беренсе дәрәжә сағыштырыуҙар

Һандар теорияһында, криптографияла һәм фәндең башҡа өлкәләрендә йыш ҡына : $ax\equiv b{\pmod {m}}.$ күренешендәге беренсе дәрәжә сағыштырыуҙарҙың сығарылышын табыу мәсьәләһе тыуа. Был сағыштырыуҙарҙы сығарыу $d=$ ИҘУБ $(a,m)$ табыуҙан башлана. Ике осраҡ булыуы мөмкин:

Әгәр $b$ $d$ -ға бүленмәһә, сағыштырыуҙың сығарылышы юҡ.
Әгәр $b$ $d$ -ға бүленһә, сағыштырыуҙың ${\frac {m}{d}}$ модуле буйынса берҙән-бер сығарылышы бар, йәки, шуны уҡ аңлата, $m$ модуле буйынса $d$ сығарылышы бар. Был осраҡта бирелгән сағыштырыуҙы $d$ -ға ҡыҫҡартыу һөҙөмтәһендә :: $a_{1}x\equiv b_{1}{\pmod {m_{1}}}$ сағыштырыуы табыла, бында

 $a_{1}={\frac {a}{d}}$ ,  $b_{1}={\frac {b}{d}}$  и  $m_{1}={\frac {m}{d}}$  бөтөн һандарбулып торалар, шуның менән бергә  $a_{1}$  һәм  $m_{1}$  үҙ-ара ябай. Шуға күрә  $a_{1}$  һанын  $m_{1}$  модуле буйынса үҙгәртергә мөмкин, йәғни  $c\cdot a_{1}\equiv 1{\pmod {m_{1}}}$  үтәлерлек  $c$  һанын табырға (икенсе төрлө,  $c\equiv a_{1}^{-1}{\pmod {m_{1}}}$ ). Сығарылышты табыу өсөн килеп сыҡҡан сағыштырыуҙы  $c$  -ға ҡабатларға кәрәк:

x\equiv ca_{1}x\equiv cb_{1}\equiv a_{1}^{-1}b_{1}{\pmod {m_{1}}}.

 $c$ -ның ҡиммәтен иҫәпләүҙе практикала төрлө ысул менән башҡарырға мөмкин: Эйлер теоремаһы, Евклид алгоритмы, кәсерҙәр сылбыры теорияһы (см. алгоритм) һ. б. ярҙамында . Айырым осраҡта, Эйлер теоремаһы   $c$ -ның ҡиммәтен:  $c\equiv a_{1}^{-1}\equiv a_{1}^{\varphi (m_{1})-1}{\pmod {m_{1}}}$  күренешендә яҙырға мөмкинлек бирә^[15].

Миҫалдар

Миҫал 1.: $4x\equiv 26{\pmod {22}}$ сағыштырыуы өсөн $d=2$ , шуға күрә 22 модуле буйынса сағыштырыуҙың ике сығарылышы бар. 26-ны уның менән 22 модуле буйынса сағыштырырлыҡ 4-кә үҙгәртәбеҙ һәм 3 һанды ла 2-гә ҡыҫҡартабыҙ:; $2x\equiv 2{\pmod {11}}$

2 һаны 11 модуле менән үҙ-ара ябай булғас, уны 11 модуле буйынса үҙгәртергә мөмкин, һәм табабыҙ: $2^{-1}\equiv 6{\pmod {11}}$ . Сағыштырыуҙы 6-ға ҡабатлап, 11 модуле буйынса сығарылыш табабыҙ:

x\equiv 1{\pmod {11}}

. Был 22 модуле буйынса ике сығарылыштың йыйылмаһына эквивалент:

x\equiv 1{\pmod {22}}

и

x\equiv 12{\pmod {22}}

.

Миҫал 2.: $100x\equiv 41{\pmod {65537}}.$ сағыштырыуы бирелгән. $65537$ модуле — ябай һан.

Сығарыуҙың беренсе ысулы - Безу нисбәте менән файҙаланыу. Евклид алгоритмы йәки Безу нисбәте тураһындағы мәҡәләлә килтерелгән программа ярҙамында $100$ һәм $65537$ һандары өсөн был нисбәттәр түбәндәге күренештә булыуын табабыҙ:

17695\cdot 100+(-27)\cdot 65537=1,

йәки

17695\cdot 100\equiv 1{\pmod {65537}}

Был сағыштырыуҙарҙың ике яғын да 41-гә ҡабатлап табабыҙ:

100\cdot 725495\equiv 41{\pmod {65537}}

Бынан $725495$ һаны бирелгән сағыштырыуҙың сығарылышы булыуы килеп сыға. Был һанды уның менән сағыштырырлыҡ булған $4588$ һанына алмаштырыу уңайлыраҡ ( $725495$ -те $65537$ -гә бүлеүҙән ҡалдыҡ). Яуап: $x\equiv 4588{\pmod {65537}}.$

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

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

37x\equiv -26855{\pmod {65537}}

Беҙ $x$ алдында 100 урынына 37 коэффициентын таптыҡ. Артабанғы һәр аҙымда ошоға оҡшаш рәүештә, берҙе тапҡанға тиклем, кәметәбеҙ.

2 аҙым. Оҡшаш рәүештә x-тың яңы коэффициентына бүләбеҙ:  $65537=37\cdot 1771+10$ . Алдағы аҙымда килеп сыҡҡан сағыштырыуҙың ике яғын да  $1771$  бүлендегенә ҡабатлайбыҙ һәм  $10x$ -ты ҡушабыҙ; һул яғын тағы ла нулгә алмаштырып, табабыҙ:

10x\equiv 47560205{\pmod {65537}}

$47560205$ -те, уны $65537,$ -гә бүлгәндәге $45880$ ҡалдығына алмаштырабыҙ:

10x\equiv 45880{\pmod {65537}}

Артабан ошоға оҡшаш тағы 5 аҙым яһарға булыр ине, ләкин сағыштырыуҙың ике яғын да 10-ға бүлергә лә, шунда уҡ яуапты табыу ябайыраҡ : $x\equiv 4588{\pmod {65537}}.$

Икенсе дәрәжә сағыштырыуҙар

Ябай m модуле буйынса икенсе дәрәжә сағыштырыуҙар түбәндәге дөйөм күренештә:

c_{0}x^{2}+c_{1}x+c\equiv 0{\pmod {m}}.

Был аңлатманы : $(x+b)^{2}\equiv a{\pmod {m}}.$ күренешенә килтерергә була, ә $z=x+b$ менән алмаштырғанда тағы ла ябайлаша:

(z)^{2}\equiv a{\pmod {m}}.

.

Был сағыштырыуҙы сығарыу (уртаҡлыҡтың квадратик законы ярҙамында) был һандың квадратик бүлеүҙән ҡалдыҡ буламы икәнен тикшереүгә һәм артабан бирелгән модуль буйынса квадрат тамырҙы табыуға ҡайтып ҡала^[16]. Квадратик бүлеүҙән ҡалдыҡтан квадрат тамырҙы иҫәпләү өсөн ихтималлыҡ Берлекэмп методы бар.

Сағыштырыуҙар системаһы

Төп мәҡәлә: Ҡалдыҡтар тураһында Ҡытай теоремаһы

Ҡалдыҡтар тураһында Ҡытай теоремаһы раҫлауынса, парлы рәүештә үҙ-ара ябай $m_{1},m_{2},\ldots ,m_{n}$ модулдәре менән сағыштырыуҙар системаһының:

{\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}}

һәр саҡ сығарылышы бар һәм ул $m_{1}\cdot m_{2}\cdots m_{n}$ модуле буйынса берҙән-бер. Икенсе һүҙ менән әйткәндә, ҡалдыҡтар тураһында Ҡытай теоремаһы, бер нисә үҙ-ара ябай һандарҙың ҡабатландығы модуле буйынса бүлеүҙән ҡалдыҡтар күмәклеге - ҡабатлашыусыларға ярашлы бүлеүҙән ҡалдыҡтар күмәклектәренең ҡабатландығы була, тип раҫлай

Ҡулланыу

Сағыштырыуҙар теорияһының методтары һандар теорияһында, төркөмдәр теорияһында, күмәклектәр теорияһында, төйөндәр теорияһында, дөйөм алгебрала, криптографияла, информатикала, химияла һәм башҡа өлкәләрҙә ҡулланыла.

Мәҫәлән, сағыштырыуҙар идентификаторҙарҙа ҡулланылған контроль суммаларҙы иҫәпләгәндә йыш ҡулланыла. Шулай, IBAN (ISO 13616)|банк иҫәбенең халыҡ-ара номерын индергәндә хатаны асыҡлау өсөн 97 модуле буйынса сағыштырыу ҡулланыла^[17]. Криптографияла сағыштырыуҙарҙы, RSA алгоритмы йәки Диффи — Хеллман протоколы ҡулланған асыҡ асҡыслы системаларҙа осратырға мөмкин. Шулай уҡ, модулле арифметика, аҙаҡ эллиптик кәкере һыҙыҡтары төҙөләсәк сикле күмәклектәрҙе тәьмин итә һәм симметрик асҡыслы төрлө протоколдарҙа ҡулланыла (AES, IDEA)^[18].

Химияла CAS регистрация номерында һуңғы цифр - номерҙың һуңғы цифрының 1-гә ҡабатландығын, уңдан икенсе цифрҙың 2-гә ҡабатландығын, өсөнсө цифрҙың 3-кә ҡабатландығын һ.б. һулдан беренсе цифрға тиклем ҡушыу юлы менән табылған һанды 10-ға бүлеүҙән килеп сыҡҡан ҡалдыҡ контроль сумманың ҡиммәте булып тора^[19]

Шулай уҡ ҡарағыҙ

Иҫкәрмәләр

↑ Вельшенбах М. Глава 5. Модулле математика: вычисление в классах вычетов. // Криптография на Си и С++ в действии.. — М. — 464 с. — ISBN 5-89392-083-X.
↑ Халыҡ-ара фәнни конференция материалдары “Модуляр арифметика” (билдәһеҙ). Виртуаль компьютер музейы (2005). Дата обращения: 31 июль 2010.
↑ Егоров А. А. Модуле буйынса сағыштырыу һәм ҡалдыҡтар арифметикаһы // Квант. — № 5.
↑ Француз математигы, 1666 йылдан Француз фәндәр академияһы ағзаһы.
↑ Вилейтнер Г. Глава III Теория чисел // История математики от Декарта до середины XIX / пер. с нем. под. ред. А. П. Юшкевича. — М.: Государственное издательство физико-математической литературы, 1960. — С. 69—84. — 467 с.
↑ ^6,0 ^6,1 Степанов С. А. Глава 1. Основные понятия // Сравнения. — М.: «Знание», 1975. — С. 3—9. — 64 с.
↑ ^7,0 ^7,1 Виноградов И. М. Основы теории чисел. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — С. 41—45. — 180 с.
↑ Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 88. — 192 с. — ISBN 978-5-9221-0741-9.
↑ ^9,0 ^9,1 ^9,2 Сагалович, 2010, с. 25—29
↑ Бухштаб А. А. Глава 8. Классы // Теория чисел. — М.: «Просвещение», 1966. — С. 77—78. — 384 с.
↑ ^11,0 ^11,1 Сагалович, 2010, с. 29—32
↑ Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 87—88,91. — 192 с. — ISBN 978-5-9221-0741-9.
↑ Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998. — С. 27 (Пример 1.37). — 430 с. — ISBN 5-03-000065-8.
↑ Фадеев Д. К. Глава VII. Сравнение в кольце полиномов и расширения полей // Лекции по алгебре. — М.: «Наука», 1984. — С. 197—198. — 416 с.
↑ Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 105—109. — 192 с. — ISBN 978-5-9221-0741-9.
↑ Бухштаб А. А. Глава 21. Сравнения 2-й степени по простому модулю, Глава 22. Сравнения второй степени по составному модулю // Теория чисел. — М.: «Просвещение», 1966. — С. 172—201. — 384 с.
↑ Harald Niederreiter, Arne Winterhof. Applied Number Theory. — «Springer», 2015. — С. 369. — 442 с. — ISBN 978-3-319-22321-6.
↑ Коблиц Н. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — С. 96, 105—109, 200—209. — 262 с. — ISBN 5-85484-012-X.
↑ Check Digit Verification of CAS Registry Numbers (ингл.).

Әҙәбиәт

Вейль А. Һандар теорияһы нигеҙҙәре. — М.: Мир, 1972.
Виленкин Н. Я. Сравнения и классы вычетов // Квант. — 1978. — № 10. — С. 4—8.
Виноградов И. М. Һандар теорияһы нигеҙҙәре. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — 180 с.
Сизый С. В. §4. Теория сравнений // Һандар теорияһы буйынса лекциялар. — Екатеринбург: Уральский государственный университет им. А. М. Горького, 1999.
Бухштаб А. А. Һандар теорияһы. — М.: «Просвещение», 1966. — 384 с.
Сагалович Ю. Л. Введение в алгебраические коды (урыҫ) — 2-е изд. — М.: ИППИ РАН, 2010. — 320 с. — ISBN 978-5-901158-14-2
Коблиц Н. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова,под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — 254 с. — ISBN 5-85484-012-X.
Материалы международной научной конференции “Модулярная арифметика” (билдәһеҙ). Виртуальный компьютерный музей (2005). Дата обращения: 31 июль 2010.

Ҡалып:Добротная статья

[1] Вельшенбах М. Глава 5. Модулле математика: вычисление в классах вычетов. // Криптография на Си и С++ в действии.. — М. — 464 с. — ISBN 5-89392-083-X.

[2] Халыҡ-ара фәнни конференция материалдары “Модуляр арифметика” (билдәһеҙ). Виртуаль компьютер музейы (2005). Дата обращения: 31 июль 2010.

[3] Егоров А. А. Модуле буйынса сағыштырыу һәм ҡалдыҡтар арифметикаһы // Квант. — № 5.

[4] Француз математигы, 1666 йылдан Француз фәндәр академияһы ағзаһы.

[5] Вилейтнер Г. Глава III Теория чисел // История математики от Декарта до середины XIX / пер. с нем. под. ред. А. П. Юшкевича. — М.: Государственное издательство физико-математической литературы, 1960. — С. 69—84. — 467 с.

[Stepanov-6] 6,0 ^6,1 Степанов С. А. Глава 1. Основные понятия // Сравнения. — М.: «Знание», 1975. — С. 3—9. — 64 с.

[Vinogradov1-7] 7,0 ^7,1 Виноградов И. М. Основы теории чисел. — М.-Л.: Гос. изд. технико-теоретической литературы, 1952. — С. 41—45. — 180 с.

[8] Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 88. — 192 с. — ISBN 978-5-9221-0741-9.

[Сагалович—2010——25—29-9] 9,0 ^9,1 ^9,2 Сагалович, 2010, с. 25—29

[10] Бухштаб А. А. Глава 8. Классы // Теория чисел. — М.: «Просвещение», 1966. — С. 77—78. — 384 с.

[Сагалович—2010——29—32-11] 11,0 ^11,1 Сагалович, 2010, с. 29—32

[12] Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 87—88,91. — 192 с. — ISBN 978-5-9221-0741-9.

[13] Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — М.: Мир, 1998. — С. 27 (Пример 1.37). — 430 с. — ISBN 5-03-000065-8.

[14] Фадеев Д. К. Глава VII. Сравнение в кольце полиномов и расширения полей // Лекции по алгебре. — М.: «Наука», 1984. — С. 197—198. — 416 с.

[15] Сизый С. В. §4. Теория сравнений // Лекции по теории чисел. — М.: ФИЗМАТЛИТ, 2008. — С. 105—109. — 192 с. — ISBN 978-5-9221-0741-9.

[16] Бухштаб А. А. Глава 21. Сравнения 2-й степени по простому модулю, Глава 22. Сравнения второй степени по составному модулю // Теория чисел. — М.: «Просвещение», 1966. — С. 172—201. — 384 с.

[17] Harald Niederreiter, Arne Winterhof. Applied Number Theory. — «Springer», 2015. — С. 369. — 442 с. — ISBN 978-3-319-22321-6.

[18] Коблиц Н. Курс теории чисел и криптографии / пер. с англ. М. А. Михайловой и В. Е. Тараканова под ред. А. М. Зубкова. — М.: Научное изд-во ТВП, 2001. — С. 96, 105—109, 200—209. — 262 с. — ISBN 5-85484-012-X.

[19] Check Digit Verification of CAS Registry Numbers (ингл.).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]