Teorema Bermahiyê ya Çînî (Chinese remainder theorem)

Di matematîkê de, teorema bermahiyê ya Çînî dibêje ku eger mirov bermahiyên dabeşkirina Euclidî ya hejmareke tam n bi çend hejmarên tam zanibe, wê demê mirov...

Di matematîkê de, teorema bermayiya Çînî diyar dike ku heke bermayiyên hejmarek tam n dema ku bi dabeşkirina Euklîdî ji hêla çend hejmarên tam ve têne dabeşkirin têne zanîn, wê demê bermayiya n dema ku bi berhema van hejmaran tê dabeşkirin dikare bi awayekî yekane were zelalkirin, bi şertê ku dabeşker bi cot hevjimar bin (ango, tu du dabeşker ji bilî 1ê faktorek hevpar nînin).

Ev teorema herwiha wekî teorema Sunzi tê zanîn. Herdu nav jî formulasyona wê ya herî kevn a belgekirî dipejirînin, ku di Sunzi Suanjing de derket holê, destnivîsek Çînî ku di navbera sedsalên 3an û 5an ên PZ de hatiye nivîsandin. Ev daxuyaniya destpêkê wekî mînakek taybet a raveker hate pêşkêş kirin:

Mînak, heke bermayiya n dema ku bi 3 tê dabeşkirin 2 be, bermayiya n dema ku bi 5 tê dabeşkirin 3 be, û bermayiya n dema ku bi 7 tê dabeşkirin 2 be, wê demê, bêyî daneyên zêde, gengaz e ku bermayiya n dema ku bi 105 (berhema 3, 5, û 7) tê dabeşkirin were zelalkirin, bêyî ku nirxa taybetî ya n çi be. Di vê rewşa taybetî de, bermayî 23 e. Herwiha, ev bermayî nirxa yekane ya hejmara tam a pozîtîf ji bo n ku ji 105 kêmtir e, temsîl dike.

Teorema bermayiya Çînî bi berfirehî di hesabkirinên ku hejmarên tam ên mezin tê de hene tê bikaranîn, ji ber ku ew dihêle ku hesabkirinek bi sînorek encamek zanîn were Rizîn kirin bo gelek hesabkirinên mîna hev ên ku hejmarên tam ên piçûktir tê de hene.

Teorema bermayiya Çînî, dema ku bi bikaranîna hevrêziyan tê îfadekirin, di nav de her qada îdeal a sereke de rast e. Prensîbên wê hatine berfirehkirin ku her zengilek keyfî bigire nav xwe, bi rêya formulasyonek ku îdealên du-alî dihewîne.

Dîrok

Daxuyaniya herî kevn a belgekirî ya vê pirsgirêkê di nivîsa sedsala 5an a Sunzi Suanjing de tê dîtin, ku ji hêla matematîkzanê Çînî Sunzi ve hatiye nivîsandin:

Hin tişt hene ku hejmara wan nenas e. Heke em wan bi sêyan bijmêrin, du dimînin; bi pêncan, sê dimînin; û bi heftan, du dimînin. Çend tişt hene?

Beşdariya Sunzi dê bi pênaseyên hemdem ên teoremekê re li hev neyê, ji ber ku ew tenê pirsgirêkek taybetî pêşkêş dike bêyî ku bişêvka wê bi berfirehî bide, îspatek giştî peyda bike, an algorîtmayek gerdûnî diyar bike. Algorîtmayek bişêvkê ji bo vê pirsgirêkê paşê ji hêla Aryabhata (sedsala 6an) ve hate berfirehkirin. Mînakên taybetî yên teorema bermayiya Çînî herwiha ji hêla Brahmagupta (sedsala 7an) ve hatin nasîn û di Liber Abaci ya Fibonacci (1202) de hatin belgekirin. Teorema paşê bi berfirehî hate giştîkirin bi bişêvkek temam ku wekî Da-yan-shu (大衍術) di nav de Mathematical Treatise in Nine Sections ya Qin Jiushao ya sala 1247an de hate binavkirin. Ev kar di destpêka sedsala 19an de ji hêla mîsyonerê Brîtanî Alexander Wylie ve bo Îngilîzî hate wergerandin.

Têgeha hevrêziyan di destpêkê de ji aliyê Carl Friedrich Gauss ve di pirtûka wî ya sala 1801ê de, Disquisitiones Arithmeticae, hate fermîkirin û bikaranîn. Gauss Teorema Bermahiyê ya Çînî bi pirsgirêkek salnameyî mînak dide, bi taybetî, "dîtina salên ku hejmareke demkî ya diyarkirî li gorî çerxa rojê û çerxa heyvî û îndîkasyona Romayî hene." Gauss ji bo vê pirsgirêkê rêbazek bişêvkê pêşkêş kir, ku her çend berê ji aliyê Leonhard Euler ve hatibû bikaranîn jî, di rastiyê de metodolojiyeke Kevnar bû ku di dirêjahiya dîrokê de dubare bûbû.

Daxuyanî

Hejmarên tam n, ..., n_k bifikirin, ku her yek ji 1ê mezintir e û bi gelemperî wekî modulî an dabeşker têne zanîn. Bila N berhema van nirxên n_i nîşan bide.

Teorema Bermahiyê ya Çînî diyar dike ku, heke n_i cot bi cot hevjimar bin, û heke a, ..., a_k hejmarên tam bin ku mercê 0 ≤ a_i < n_i ji bo her i têr dikin, wê demê hejmareke tam a Bêhempa x heye ku 0 ≤ x < N, û ji bo her i, bermahiya dabeşkirina Euklîdî ya x bi n_i re a_i ye.

Di zimanê hevrêziyan de, ev dikare wiha were vegotin: Heke $n_{i}$ cot bi cot hevjimar bin, û heke a24, ..., a_k hejmarên tam ên keyfî nîşan bidin, wê demê pergal

{\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}

23 ( mod n 40 ) ⋮ x ≡ a k ( mod n k ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}

Bişêvkek heye, û her du bişêvkên cuda, wekî x û x§6_{7§, li gorî modul N hevrêz in, ango x ≡ x§17_{18§ (mod N )}.}

Di nav qada cebîra razber de, ev teorîm bi gelemperî wiha tê ji nû ve formulekirin: heke hejmarên tam n_i cot bi cot hevjimar bin, wê demê nexşekirin

x{\bmod {N}}\;\mapsto \;(x{\bmod {n}}_{1},\,\ldots ,\,x{\bmod {n}}_{k})

37 , … , x mod n k ) {\displaystyle x{\bmod {N}}\;\mapsto \;(x{\bmod {n}}_{1},\,\ldots ,\,x{\bmod {n}}_{k})}

îzomorfîzmek zengilê saz dike.

\mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z}

35 Z × ⋯ × Z / n k Z {\displaystyle \mathbb {Z} /N\mathbb {Z} \cong \mathbb {Z} /n_{1}\mathbb {Z} \times \cdots \times \mathbb {Z} /n_{k}\mathbb {Z} }

Teorema Bermahiyê ya Çînî îzomorfîzmekê di navbera zengila hejmarên tam modulo N û berhema rasterast a zengilên hejmarên tam modulo n_i de saz dike. Wekî encam, rêzek ji operasyonên arîtmetîkî Di nav $\mathbb {Z} /N\mathbb {Z} ,$ de dikare bi cîbicîkirina heman hesabkirinan bi serbixwe di her $\mathbb {Z} /n_{i}\mathbb {Z}$ de were kirin, û dûv re encama dawîn bi sepandina îzomorfîzma berevajî were bidestxistin. Ev nêzîkatî dikare hesabkirinan Bi awayekî girîng lez bike, nemaze dema ku N û hejmara operasyonan zêde bin. Ev Teknîk, ku wekî hesabkirina pir-modular tê zanîn, Bi berfirehî di cebîra xêzî de ku hejmarên tam an hejmarên rasyonel dihewîne tê bikaranîn.

Di warê kombînatorîkê de, teorem dikare were ji nû ve formulekirin da ku bêje ku rêzên arîtmetîkî yên Bêdawî yên hejmarên tam malbatek Helly pêk tînin.

Îspat

Hebûn û yekanebûna Bişêvkê dikare bi serbixwe were îspatkirin. Lêbelê, îspata destpêkê ya Hebûnê, ku paşê tê pêşkêşkirin, xwe dispêre vê yekanebûnê.

Yekanebûn

Bifikirin ku hem x û hem jî y hemî kongruensên diyarkirî têr dikin. Ji wê demê ve x û y dema ku ji hêla her n_i ve têne dabeş kirin bermayiyên yekbûyî didin, cûdahiya wan, x − y, divê pirjimara her n_i be. Ji ber ku n_i cot bi cot hevjimar in, berhema wan N jî x − y dabeş dike, ku tê wateya ku x û y modulo N kongruent in. Ger x û y bi neyînî û bi tundî ji N kêmtir bin (wekî ku di formulasyona destpêkê ya teoremê de hatî destnîşan kirin), wê demê cûdahiya wan tenê dikare pirjimara N be heke û tenê heke x = y be.

Hebûn (Îspata Destpêkê)

Nexşekirin

x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})

32 , … , x mod n k ) {\displaystyle x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})}

Ev veguherîn çînên lihevhatinê yên modulo N diguherîne rêzikên çînên lihevhatinê yên modulo n_i. Îspata yekanebûnê înjeksîvîteya vê nexşeyê destnîşan dike. Ji wê demê ve ku domên û kodomên xwedî hejmareke wekhev a hêmanan in, nexşe herwiha surjektîv e, bi vî awayî hebûna bişêvkekê destnîşan dike.

Her çend hêsan be jî, ev îspat ji bo hesabkirina bişêvkekê rêbazeke rasterast pêşkêş nake. Herwiha, ew kêmasiya giştîkirinê ji bo çarçoveyan heye ku îspata paşîn tê de derbasdar e.

Hebûn (Îspata Avakar)

Hebûna x dikare bi rêya avakariyeke eşkere were nîşandan. Ev avakarî du gavên sereke dihewîne: di destpêkê de çareserkirina pirsgirêkê ji bo du modulan, û paşê berfirehkirina vê bişêvkê ji bo rewşa giştî bi rêya biderxistinê li ser hejmara modulan.

Rewşa Du-Modulan

Armanc ew e ku pergala jêrîn were çareserkirin:

Pergala lihevhatinan wiha tê pênasekirin:

{\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}

23 ( mod n 40 ) x ≡ a

{\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}

( mod n

{\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}

) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\x&\equiv a_{2}{\pmod {n_{2}}},\end{aligned}}} .

Di vê çarçoveyê de, $n_{1}$ 10 {\displaystyle n_{1}} û $n_{2}$ {\displaystyle n_{2}} wek hejmarên hevseretayî têne destnîşankirin.

Li gorî nasnameya Bézout, du hejmarên tam hene, bi taybetî $m_{1}$ 10 {\displaystyle m_{1}} û $m_{2}$ {\displaystyle m_{2}} , ku mercê jêrîn têr dikin:

m_{1}n_{1}+m_{2}n_{2}=1.

10 n 18 + m

m_{1}n_{1}+m_{2}n_{2}=1.

m_{1}n_{1}+m_{2}n_{2}=1.

= 1. {\displaystyle m_{1}n_{1}+m_{2}n_{2}=1.}

Van hejmarên tam, $m_{1}$ 10 {\displaystyle m_{1}} û $m_{2}$ {\displaystyle m_{2}} , dikarin bi sepandina algorîtma Euklîdî ya berfirehkirî werin derxistin.

Bişêvkek taybet wekî encam wiha tê îfadekirin:

x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.

14 m

x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.

x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.

+ a

x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.

m 48 n 56 . {\displaystyle x=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}.}

Ev îdîa bi ya jêrîn tê piştrastkirin:

{\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}

22 m

{\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}

{\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}

+ a

{\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}

m 56 n 64 = a 82 ( 88 − m §9798§ n §105106§ ) + a §117

{\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}

m §125126§ n §133134§ = a 151 + ( a

{\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}

− a 174 ) m 184 n 192 , {\displaystyle {\begin{aligned}x&=a_{1}m_{2}n_{2}+a_{2}m_{1}n_{1}\\&=a_{1}(1-m_{1}n_{1})+a_{2}m_{1}n_{1}\\&=a_{1}+(a_{2}-a_{1})m_{1}n_{1},\end{aligned}}}

Ev tê wê wateyê ku $x\equiv a_{1}{\pmod {n_{1}}}.$ 15 ( mod n 32 ) . {\displaystyle x\equiv a_{1}{\pmod {n_{1}}}.} Delîleke wekhev hevgirtina duyemîn jî piştrast dike, ku bi cîguhertina jêrnîşanan 1 û 2 pêk tê.

Rewşa Giştî

Em rêzek hevkêşeyên hevgirtinê bifikirin:

{\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}

23 ( mod n 40 ) ⋮ x ≡ a k ( mod n k ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}

Modulên $n_{i}$ hevdu-seretayî ne. Bişêvkek, ku wekî $a_{1,2}$ 32 , §36 $n_{i}$ {\displaystyle a_{1,2}} tê nîşandan, ji bo du hevkêşeyên destpêkê dikare bi bikaranîna rêbaza ku di beşa berê de hatibû ravekirin, were bidestxistin. Koma bişêvkan ji bo van du hevkêşeyên destpêkê, bi koma temam a bişêvkan ji bo hevkêşeya jêrîn re li hev tê:

x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.

15 , §19

x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.

( mod n 36 n

x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.

) . {\displaystyle x\equiv a_{1,2}{\pmod {n_{1}n_{2}}}.}

Ji ber ku modulên mayî $n_{i}$ bi berhema $n_{1}n_{2},$ 32 n $n_{i}$ , {\displaystyle n_{1}n_{2},} re hevdu-seretayî ne, ev bi bandor pirsgirêka resen, ku tê de k hevkêşe hene, diguherîne bo pirsgirêkek mîna wê ku ji $k-1$ 67 {\displaystyle k-1} hevkêşeyan pêk tê. Bi sepandina dubarekirî ya vê Pêvajoyê, bişêvkên pirsgirêka destpêkê Di encamê de têne bidestxistin.

Hebûn: Avakirina Rasterast

Dema ku Bişêvkek tê avakirin, nêzîkatiyek înduktîf ku li ser hejmara modulan bingeh digire, bi tundî ne hewce ye. Lêbelê, ev rêbaza avakirina rasterast bi gelemperî hesabkirinên berfireh ku hejmarên mezin dihewînin pêk tîne, bi vî awayî karîgerî û belavbûna wê kêm dike. Hêjayî gotinê ye ku înterpolasyona Lagrange nimûneyek taybetî ya vê avakirinê temsîl dike, ku ji bo polînoman li şûna hejmarên tam hatiye adaptekirin.

Bila $N_{i}=N/n_{i}$ berhema hemî modulan be, ji bilî yekê. Ji ber ku $n_{i}$ cot bi cot hevjimar in, ev tê wê wateyê ku $N_{i}$ û $n_{i}$ jî hevjimar in. Wekî encam, nasnameya Bézout dikare were sepandin, ku Hebûn a hejmarên tam $M_{i}$ û $m_{i}$ ku Merc a jêrîn bicîh tînin, garantî dike:

M_{i}N_{i}+m_{i}n_{i}=1.

Bişêvkek ji bo vê Pergal a hevrêziyan wiha tê pênasekirin:

x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.

19 k a i M i N i . {\displaystyle x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.}

Bi rastî, Ji wê demê ve $N_{j}$ pirjimarek ji $n_{i}$ pêk tîne dema ku $i\neq j,$ ev tê wê wateyê ku:

x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},

48 − m i n i ) ≡ a i ( mod n i ) , {\displaystyle x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},}

Ev hevrêzî ji bo her $i.$ derbasdar e.

Hesabkirin

Pergal a hevrêziyan bifikirin:

{\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\\\end{aligned}}

23 ( mod n 39 ) ⋮ x ≡ a k ( mod n k ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\\\end{aligned}}}

Li vir $n_{i}$ hevdu-asal in. Bila $N=n_{1}n_{2}\cdots n_{k}.$ 36n $n_{i}$ ⋯nk.{\displaystyle N=n_{1}n_{2}\cdots n_{k}.} Ev beş çend rêbazên hesabkirinê yên ji bo dîtina Bişêvk a Bêhempa ya $x$ , ku bi Merc a $0\leq x<N,$ 92§≤x<N,{\displaystyle 0\leq x ve girêdayî ye, bi hûrgulî rave dike. Ev metodolojî dê paşê bi mînakek taybetî werin nîşandan.

{\begin{aligned}x&\equiv 0{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 4{\pmod {5}}.\end{aligned}}

19(mod§3031§)x≡48(mod§5960§)x≡78(mod88).{\displaystyle {\begin{aligned}x&\equiv 0{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 4{\pmod {5}}.\end{aligned}}}

Ev beş çend metodolojiyên hesabkirinê destnîşan dike. Du nêzîkatiyên destpêkê ji bo mînakên Pûlik-biçûk guncan in, lê dema ku berhema $n_{1}\cdots n_{k}$ 10⋯nk{\displaystyle n_{1}\cdots n_{k}} mezin dibe, bêkêrîyek girîng nîşan didin. Berovajî, rêbaza sêyemîn, ku delîla Hebûn a avaker a ku di § Existence (constructive proof) de hatî hûrgulîkirin bikar tîne, ji bo berhemên mezin an ji bo pêkanîna di algorîtmayên komputerê de herî bikêr tê.

Lêgerîna Sîstematîk

Verastkirina ka nirxek x Bişêvkek e, hêsan e: tenê pêdivî ye ku bermayiya dabeşkirina Euklîdî ya x bi her n_i were hesabkirin. Wekî encam, ji bo dîtina Bişêvkê, bes e ku hejmarên ji 12 heta N bi rêzê werin lêkolîn kirin Heta ku Bişêvk a rast were dîtin.

Tevî sadebûna xwe, ev rêbaz bêkêmasiyek bi awayekî girîng nîşan dide. Di mînaka taybet a hatî dayîn de, tespîtkirina bişêvkê, ku 39 ye, pêdivî bi lêkolîna 40 hejmarên tam heye, di nav de 4. Ev algorîtmayek dema eksponensîel pêk tîne ji ber ku mezinahiya têketinê, bêyî ku faktorek Berdewam were hesibandin, bi hejmara reqeman di N de têkildar e, û hejmara operasyonên navînî nêzî Rêkûpêkiya N dibe.

Wekî encam, ev nêzîkatî hem di hesabkirinên destan de hem jî di Pêvajoyên hesabkeriyê de kêm tê bikaranîn.

Lêgerîna Li ser bingeha Sîvekirinê

Sîvekirin dikare Pêvajoya dîtina bişêvkekê bi awayekî girîng lez bike. Ji bo vê Teknîkê, em, Bêyî windakirina giştîbûnê, texmîn dikin ku $0\leq a_{i}<n_{i}$ 6 ≤ a i < n i {\displaystyle 0\leq a_{i}} . (Wekî din, dê bes be ku her $a_{i}$ bi bermayiya ku ji dabeşkirina wê bi $n_{i}$ ve hatî bidestxistin were guhertin). Ev Merc destnîşan dike ku bişêvk endamek ji rêza aritmetîkî ya jêrîn e:

a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots

10 , a 20 + n 30 , a 40 +

a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots

53§ , … {\displaystyle a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots }

Bi nirxandina van hejmaran modulo $n_{2},$ , {\displaystyle n_{2},} , bişêvkek $x_{2}$ {\displaystyle x_{2}} ji bo du hevgirtinên destpêkê Di encamê de tê tespîtkirin. Dûv re, bişêvk dibe beşek ji rêza aritmetîkî ya jêrîn:

x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots

, x

x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots

+ n 30 n

x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots

, x

x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots

x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots

61§ n §68

x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots

, … {\displaystyle x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots }

Bişêvk Di encamê de tê bidestxistin bi ceribandina nirxên van hejmaran modulo $n_{3},$ , û bi Pêvajoyek dubarekirî Heta ku hemî modûl hatine nirxandin.

Ev rêbaz dema ku modul bi rêkûpêkîya daketî hatine rêzkirin, bi taybetî heke $n_{1}>n_{2}>\cdots >n_{k}.$ 10 > n ${\displaystyle n_{1}>21§ </mrow> </msub> <mo>></mo> <mo>⋯</mo> <mo>></mo> <msub> <mi>n</mi> <mrow class=$ . {\displaystyle n_{1}>n_{2}>\cdots >n_{k}.} , karîgeriyeke zêde nîşan dide. Sepandina vê li ser mînaka hatî dayîn, gavên hesabkirinê yên jêrîn dide. Di destpêkê de, hejmarên ku bi 4 modulo 5 re hevaheng in (modula herî mezin) têne lêkolîn kirin, di nav de 4, 9 = 4 + 5, û 14 = 9 + 5. Ji bo her yek ji van, bermayiya modulo 4 (modula duyemîn a herî mezin) tê hesibandin heta ku hejmarek ku bi 3 modulo 4 re hevaheng e were bidestxistin. Dûv re, pêvajo lêzêdekirina 20 = 5 × 4 bi awayekî gav bi gav pêk tîne û tenê bermayiyên modulo 3 dihesibîne. Ev rêbaz encam dide:

4 modulo 4, 0 dide. Berdewam bike.

4 + 5 = 9, ku 1 modulo 4 e. Berdewam bike.

9 + 5 = 14, ku 2 modulo 4 e. Berdewam bike.

14 + 5 = 19, ku 3 modulo 4 e. Ev encam tê qebûlkirin; pêvajo bi nirxandina bermayiyên modulo 3 û lêzêdekirina 5 × 4 = 20 di her gava paşîn de berdewam dike.

19 modulo 3, 1 dide. Berdewam bike.

19 + 20 = 39, ku 0 modulo 3 e. Ev, bişêvka dawîn temsîl dike.

Ev nêzîkatî ji bo hesabên destan ên ku hilberek nerm a modulan tê de heye, bi bandor e. Lêbelê, performansa wê bi awayekî girîng li paş rêbazên alternatîf dimîne dema ku bi hilberên modulan ên pir mezin re mijûl dibe. Tevî ku li gorî teknîkên lêgerîna sîstematîk pêşkeftinek lezê ya girîng pêşkêş dike, ev rêbaz tevliheviya demê ya eksponensîyel nîşan dide, ku ew ji bo bicihanîna hesabkeriyê negunca dike.

Sepandina Avakirina Hebûnê

Îspata Hebûna avaker nîşan dide ku ji bo du modulan, Bişêvkek dikare were bidestxistin bi hesabkirina hejmarên Bézout ên van modulan, dûv re rêzek pirjimarî, kombûn û kêmkirinên modulo $n_{1}n_{2}$ 10 n $n_{1}n_{2}$ {\displaystyle n_{1}n_{2}} , da ku encam Di nav de navbera $(0,n_{1}n_{2}-1)$ 38 , n §4647§ n §54 $n_{1}n_{2}$ − §6162§ ) {\displaystyle (0,n_{1}n_{2}-1)} bimîne. Ji wê demê ve hejmarên Bézout bi Algorîtma Euklîdî ya berfirehkirî têne hesabkirin, tevahiya Pêvajo ya hesabkirinê tevliheviyek dema çargoşeyî ya herî zêde ya $O((s_{1}+s_{2})^{2}),$ 89 + s $n_{1}n_{2}$ ) $n_{1}n_{2}$ ) , {\displaystyle O((s_{1}+s_{2})^{2}),} nîşan dide, li vir $s_{i}$ hejmara reqeman Di nav de $n_{i}.$ ye.

Dema ku bi zêdetirî du modulan re mijûl dibin, rêbaza damezrandî ya ji bo du modulan guhertina her cotek lihevkirinan bi lihevkirinek yekane gengaz dike, ku modula wê berhema her du yên orîjînal e. Serlêdana dubare ya vê Pêvajo Di encamê de Bişêvkek dide ku tevliheviyek hesabkirinê ya çargoşeyî li gorî hejmara reqeman Di nav de berhema hemî modulan heye. Bi awayekî balkêş, ev tevliheviya dema çargoşeyî neguher dimîne, bêyî ku rêza ku modulan tê de têne hev kirin. Nêzîkatiyek Berbelav Di destpêkê de tê de hevgirtina du modulên yekem, dûv re yekkirina modula encam bi ya din re, û berdewamkirina vê Pêvajo ya dubare ye. Her çend ev stratejî pêkanînek hêsan pêşkêş dike jî, ew hewcedariya hesabkirinên berfireh dike ku nirxên hejmarî yên her ku diçe mezintir tê de hene.

Stratejiyek alternatîf tê de dabeşkirina modulan li cotan e ku berhemên mezinahiyên Nêzîkî wekhev hene, dûv re bi hevdemî sepandina rêbaza du-modulan li her cotekê, û dûv re dubarekirina Pêvajo bi komek modulên kêmkirî, ku hejmara wan Nêzîkî nîvî bûye. Ev nêzîkatî Bi awayekî girîng paralelkirina Algorîtma hêsan dike. Herwiha, dema ku algorîtmayên Bilez (bi taybetî, yên ku di dema quasilinear de dixebitin) ji bo operasyonên Bingehîn têne bikar anîn, ev rêbaz dihêle ku tevahiya hesabkirinê di dema quasilinear de were kirin.

Ji bo mînaka Niha, ku tenê sê modul tê de hene, her du stratejiyên jorîn li hev dicivin û bi heman awayî dimeşin.

Nasnameya Bézout ji bo hejmarên 3 û 4 wiha tê îfadekirin:

1\times 4+(-1)\times 3=1.

6 × §1112§ + ( − §2021§ ) × §2728§ = 1. {\displaystyle 1\times 4+(-1)\times 3=1.}

Bi cihkirina van nirxan di nav formulê de, ku berê ji bo nîşandana Hebûnê hatibû damezrandin, ev encam dide:

0\times 1\times 4+3\times (-1)\times 3=-9

6 × §1112§ × §1617§ + §2021§ × ( − §3031§ ) × §3738§ = − §4445§ {\displaystyle 0\times 1\times 4+3\times (-1)\times 3=-9}

Ev encam Bişêvkekê ji bo du hevgirtinên destpêkê temsîl dike; hemî Bişêvkên din bi lêzêdekirina her pirjimarek ji 3 × 4 = 12 li −9 têne bidestxistin. Her çend her yek ji van Bişêvkan dikare were bikaranîn jî, Bişêvk 3 = −9 +12 ji ber nirxa wê ya mutleq a piçûktir tê tercîhkirin, ku dibe ku hesabkirinên paşîn hêsan bike.

Nasnameya Bézout ji bo hejmarên 5 û 3 × 4 = 12 wiha tê dayîn:

5\times 5+(-2)\times 12=1.

Ji nû ve sepandina heman formulê Bişêvkekê ji bo pirsgirêkê dide:

5\times 5\times 3+12\times (-2)\times 4=-21.

Bişêvkên din bi tevlêkirina her pirjimarek ji 3 × 4 × 5 = 60 têne bidestxistin, digel ku Bişêvka herî piçûk a pozîtîf −21 + 60 = 39 ye.

Nîşandan wekî Pergalek Diophantine ya Xêzî

Pergala hevgirtinan ku ji hêla Teorema Bermahiyê ya Çînî ve tê çareserkirin, dikare wekî Pergalek hevkêşeyên Diophantine yên xêzî ji nû ve were formulekirin:

{\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}

22 + x 32 n 40 ⋮ x = a k + x k n k , {\displaystyle {\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}}

Li vir, hejmarên tam ên Nenas $x$ û guhêrbar $x_{i}.$ Wekî encam, her rêbazeke giştî ji bo çareserkirina pergalên wisa, di nav de kêmkirina matrisa Pergalê bo Forma normal a Smith an Forma normal a Hermite, dikare were bikaranîn da ku Bişêvk a Teorema Bermayî ya Çînî were diyarkirin. Lê belê, li gor encama asayî ya bikaranîna Algorîtmayeke giştî li ser pirsgirêkeke taybet, ev stratejî kêmtir bi bandor derdikeve ji nêzîkatiya ku di beşa berê de hatî hûrgilîkirin, ku rasterast xwe dispêre nasnameya Bézout.

Li ser Domenên Îdeal ên Serekî

Teorema Bermayî ya Çînî, wekî ku di beşa § Statement de hatiye pêşkêşkirin, bi sê Formên cuda hatiye vegotin: bi bikaranîna bermayî, lihevkirin û îzomorfîzma zengilê. Bi gelemperî, Forma ku bermayiyan dihewîne ji bo domenên îdeal ên serekî nayê bikaranîn, ji ber ku bermayî Di nav van zengilan de pênaseya wan tune. Lê belê, du versiyonên din Di nav domena îdeal a serekî R de derbasdar dimînin; ev hewce dike ku "hejmara tam" bi "Elementa domenê" were guhertin û $\mathbb {Z}$ bi R were guhertin. Van her du versiyonên teoremê di vê Çarçoveyê de rast in ji ber ku îspatên wan, bi Îstîsnaya îspata Hebûnê ya destpêkê, ji lemmaya Euclid û nasnameya Bézout derdikevin, ku her du jî li seranserê hemî domenên serekî derbasdar in.

Bi gelemperî, Lê belê, teorem tenê wekî teoremeke Hebûnê tevdigere, ku rêbazeke eşkere ji bo hesabkirina Bişêvkê pêşkêş nake heya ku Algorîtmayek ji bo diyarkirina hevkêşeyên nasnameya Bézout peyda nebe.

Li ser Zengilên Polînomî yên Yek-guhêrbar û Domenên Euclidî

Daxuyaniya li ser bermayiyan ku di § Theorem statement de hatiye pêşkêşkirin nikare bi gerdûnî li ser hemî domenên îdeal ên serekî were giştîkirin; Lê belê, berfirehkirina wê bo domenên Euclidî hêsan e.

Teorema Bermayî ya Çînî ji bo polînomiyan dikare bi awayekî fermî wiha were gotin: Bila $P_{i}(X)$

Avakirina Bişêvkê dikare bi rêbazên ku di § Hebûn (îspata avaker) an § Hebûn (îspata rasterast) de hatine hûrgilîkirin were bidestxistin. Lê belê, nêzîkatiya îspata rasterast dikare were hêsankirin bi bikaranîna Rizîna perçeyî ya kasiran li şûna Algorîtmayeke Euclidî ya berfireh.

Wekî encam, armanc ew e ku polînomek $P(X)$ were diyarkirin ku lihevkirinên jêrîn têr dike:

P(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},

ji bo $i=1,\ldots ,k.$ 10 , … , k . {\displaystyle i=1,\ldots ,k.}

Polînomên jêrîn bifikirin:

{\begin{aligned}Q(X)&=\prod _{i=1}^{k}P_{i}(X)\\Q_{i}(X)&={\frac {Q(X)}{P_{i}(X)}}.\end{aligned}}

k P i ( X ) Q i ( X ) = Q ( X ) P i ( X ) . {\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}P_{i}(X)\\Q_{i}(X)&={\frac {Q(X)}{P_{i}(X)}}.\end{aligned}}}

Rizîna perçeyî ya kesran a $1/Q(X)$ k polînom, bi taybetî $S_{i}(X)$ $\deg S_{i}(X)<d_{i},$

{\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {S_{i}(X)}{P_{i}(X)}},

Wekî encam,

1=\sum _{i=1}^{k}S_{i}(X)Q_{i}(X).

Ji ber vê yekê, bişêvkek ji pergala hevahengî ya hevdem bi polînomê tê nîşandan:

\sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X).

Bi rastî, em çavdêrî dikin:

\sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X)=A_{i}(X)+\sum _{j=1}^{k}(A_{j}(X)-A_{i}(X))S_{j}(X)Q_{j}(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},

15 k A i ( X ) S i ( X ) Q i ( X ) = A i ( X ) + ∑ j = 92 k ( A j ( X ) − A i ( X ) ) S j ( X ) Q j ( X ) ≡ A i ( X ) ( mod P i ( X ) ) , {\displaystyle \sum _{i=1}^{k}A_{i}(X)S_{i}(X)Q_{i}(X)=A_{i}(X)+\sum _{j=1}^{k}(A_{j}(X)-A_{i}(X))S_{j}(X)Q_{j}(X)\equiv A_{i}(X){\pmod {P_{i}(X)}},}

ji bo $1\leq i\leq k.$ 6 ≤ i ≤ k . {\displaystyle 1\leq i\leq k.}

Ev bişêvk dibe ku pileya wê ji $D=\sum _{i=1}^{k}d_{i}.$ 19kdi.{\displaystyle D=\sum _{i=1}^{k}d_{i}.} zêdetir be. Bişêvka Bêhempa, ku pileya wê ji $D$ $B_{i}(X)$ $A_{i}(X)S_{i}(X)$ $P_{i}(X).$

P(X)=\sum _{i=1}^{k}B_{i}(X)Q_{i}(X).

25kBi(X)Qi(X).{\displaystyle P(X)=\sum _{i=1}^{k}B_{i}(X)Q_{i}(X).}

Înterpolasyona Lagrange

Înterpolasyona Lagrange nimûneyek taybet a teorema bermayiyê ya Çînî ji bo polînoman e. Ji bo vê sepandinê, k polînomên monîk bifikirin, ku her yek ji wan bi pileya yekê ye:

P_{i}(X)=X-x_{i}.

Ev polînom hevdu-koprîm in heke hemî nirxên $x_{i}$ cuda bin. Li gorî teorema bermayiyê ya polînomî, bermayiyê ku ji dabeşkirina polînomek $P(X)$ bi $P_{i}(X)$ tê bidestxistin $P(x_{i})$ ye.

Bila $A_{1},\ldots ,A_{k}$ 10 , … , A k {\displaystyle A_{1},\ldots ,A_{k}} sabitiyan temsîl bikin, ku ew polînomên bi pileya 0 ne, di nav $K.$ Hem înterpolasyona Lagrange û hem jî teorema bermayiyê ya Çînî hebûna polînomek Bêhempa $P(X),$ , bi pileyek kêmtir ji $k$ , saz dikin, bi awayekî ku:

P(x_{i})=A_{i},

ji bo her $i.$

Di vê çarçoveya taybet de, formula înterpolasyonê ya Lagrange bi rastî li hev tê bi encama ku ji avakirina bişêvkê ya ku berê hatibû behskirin hatiye wergirtin. Ji bo zelalkirinê, bifikirin:

{\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}

33 k ( X − x i ) Q i ( X ) = Q ( X ) X − x i . {\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}}

Rizîna perçeyî ya kasiran a ${\frac {1}{Q(X)}}$ 8 Q ( X ) {\displaystyle {\frac {1}{Q(X)}}} wiha ye:

{\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}.

8 Q ( X ) = ∑ i = 33 k 43 Q i ( x i ) ( X − x i ) . {\displaystyle {\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}.}

Dema aliyê rastê bo denomaînatorê berbelav tê kêmkirin, îfadeya jêrîn tê bidestxistin:

\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}={\frac {1}{Q(X)}}\sum _{i=1}^{k}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}},

15 k 25 Q i ( x i ) ( X − x i ) = 72 Q ( X ) ∑ i = 95 k Q i ( X ) Q i ( x i ) , {\displaystyle \sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}={\frac {1}{Q(X)}}\sum _{i=1}^{k}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}},}

Hejmar, ji ber bûyîna polînomekê ku pileya wê ji $k,$ kêmtir e, nirxa yekê digire. Ev çêdibe ji ber ku ew ji bo $k$ nirxên cuda yên $X.$ nirxa yekê digire.

Sepandina formula giştî ya ku berê hatibû behskirin, formula înterpolasyonê ya Lagrange encam dide:

P(X)=\sum _{i=1}^{k}A_{i}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}.

25 k A i Q i ( X ) Q i ( x i ) . {\displaystyle P(X)=\sum _{i=1}^{k}A_{i}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}.}

Înterpolasyona Hermite

Înterpolasyona Hermite serîlêdanek Teorema Bermahiyê ya Çînî ye, ku bi taybetî ji bo polînomên yek-guhêrbar hatiye çêkirin û rêbazek e ku dikare modulên bi dereceyên keyfî têxe nav xwe. Ev berevajî înterpolasyona Lagrange ye, ku tenê bi modulên dereceyê yek sînorkirî ye.

Armanca vê pirsgirêkê ev e ku polînomek bi dereceya herî kêm a gengaz were diyarkirin, bi awayekî ku hem polînom û hem jî derîvatîvên wê yên destpêkê nirxên diyarkirî li xalên sabît ên destnîşankirî bigirin.

Ji bo ku ev bi rastî zelaltir bibe, bila $x_{1},\ldots ,x_{k}$ 10,…,xk{\displaystyle x_{1},\ldots ,x_{k}} $k$ endamên ji qada bingehîn $K,$ $i=1,\ldots ,k,$ 82§,…,k,{\displaystyle i=1,\ldots ,k,} bila $a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}$ 117§,ai,§130131§,…,ai,ri−§159160§{\displaystyle a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}} nirxên yekem $r_{i}$ derîvatîvên polînomê xwestî ku li $x_{i}$ $P(X)$ were diyarkirin, bi awayekî ku derîvatîva wê ya j-emîn nirxa $a_{i,j}$ li $x_{i},$ bigire, ji bo hemî $i=1,\ldots ,k$ 301§,…,k{\displaystyle i=1,\ldots ,k} û $j=0,\ldots ,r_{j}.$ 330§,…,rj.{\displaystyle j=0,\ldots ,r_{j}.}

Niha, polînomê bifikirin

P_{i}(X)=\sum _{j=0}^{r_{i}-1}{\frac {a_{i,j}}{j!}}(X-x_{i})^{j}.

31 r i − 46 a i , j j ! ( X − x i ) j . {\displaystyle P_{i}(X)=\sum _{j=0}^{r_{i}-1}{\frac {a_{i,j}}{j!}}(X-x_{i})^{j}.}

Ev îfade polînoma Taylor ya rêkûpêkî $r_{i}-1$ 17 {\displaystyle r_{i}-1} ku li dora $x_{i}$ hatiye navendkirin, û ku têkildar e bi polînoma Nenas $P(X).$ Wekî encam, mercê jêrîn divê were bicîhanîn:

P(X)\equiv P_{i}(X){\pmod {(X-x_{i})^{r_{i}}}}.

Berovajî, her polînomek $P(X)$ ku van $k$ lihevhatinan têr dike, dê bi rastî ji bo hemî $i=1,\ldots ,k$ 48 , … , k {\displaystyle i=1,\ldots ,k} piştrast bike.

P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}

64 {\displaystyle P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}}

Wekî encam, $P_{i}(X)$ $r_{i}-1$ $x_{i}$ $P(X)$ $r_{i},$ $k$

Ji bo hesabkirina bişêvkê $P(X).$

Giştîkirina bo Modulên Ne-Hevjimar

Teorema Bermahiyê ya Çînî dikare were giştîkirin da ku modulên ne-hevjimar jî bigire nav xwe.

Bila $n_{1},\dots ,n_{k}$ $a_{1},\dots ,a_{k}$

Vê pergal a hevgirtinan bifikirin:

{\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}

23 ( mod n 40 ) ⋮ x ≡ a k ( mod n k ) , {\displaystyle {\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}}

Hebûna bişêvkekê ji bo vê pergalê tenê û tenê heke, ji bo hemî îndeksên cuda $\gcd(n_{i},n_{j})$ ferqa $a_{i}-a_{j}$ parçe bike, li cihê ku $i\neq j.$

Heke ev merc pêk were, koma bişêvkan çînek hevgirtinê ya bêhempa modulo $N={\text{lcm}}(n_{1},\dots ,n_{k}).$ 20 , … , n k ) . {\displaystyle N={\text{lcm}}(n_{1},\dots ,n_{k})} pêk tîne. Ev tê wê wateyê ku her du bişêvkên cuda bi pirjimarek ji $N$ ji hev cuda ne, û lêzêdekirina pirjimarek ji $N$ li bişêvkekê dê her dem bişêvkek din a derbasdar bide.

Ji bo ku ev têgeh ji bo pergalek ku du hevrêziyan dihewîne were nimûne kirin, bifikirin ku $m,n$ hejmarên pozîtîf in û $a,b$ hejmarên keyfî ne. $g=\gcd(m,n)$ wek dabeşkera herî mezin a berbelav û $M=\operatorname {lcm} (m,n)$ wek pirjimara herî biçûk a berbelav pênase bikin. Dûv re, pergala jêrîn a hevrêziyan bifikirin:

{\begin{aligned}x&\equiv a{\pmod {m}}\\x&\equiv b{\pmod {n}},\end{aligned}}

Pergal xwedî bişêvkek Bêhempa ye modulo $M=mn/g$ eger merca $a\equiv b{\pmod {g}}$ were bicihanîn; wekî din, tu bişêvk tune.

Bi karanîna nasnameya Bézout ji bo îfadekirina $g=um+vn$ , bişêvkek taybet dikare wiha were formulekirin:

x={\frac {avn+bum}{g}}.

Ev îfade nirxek tam dide ji ber ku g dabeşkerek hem ji m û hem jî ji n ye.

Giştîkirin bo Zengilên Keyfî

Teorema Bermahiyê ya Çînî bi sepandina îdealên hevpêş, ku wekî îdealên komaksîmal jî têne zanîn, berfireh dibe bo her zengilekê. Du îdeal, I û J, wekî hevpêş têne pênasekirin heke elementên $i\in I$ û $j\in J$ hebin ku berhema wan yek be: $i+j=1.$ Ev têkiliya taybet bi awayekî analogîkî wekî nasnameya Bézout di nav îsbatên ku bi vê giştîkirinê ve girêdayî ne de kar dike, yên ku wekî din dişibin hev. Daxuyaniya fermî ya vê giştîkirinê li jêr tê pêşkêşkirin.

Bila I3, ..., I_k wek îdealên du-alî di nav de zengilek $R$ bêne hesibandin, û bila I hevbirîna wan nîşan bide. Ger ev îdeal cot-bi-cot hevpar-seretayî bin, îzomorfîzma jêrîn pêk tê:

{\begin{aligned}R/I&\to (R/I_{1})\times \cdots \times (R/I_{k})\\x{\bmod {I}}&\mapsto (x{\bmod {I}}_{1},\,\ldots ,\,x{\bmod {I}}_{k}),\end{aligned}}

36 ) × ⋯ × ( R / I k ) x mod I ↦ ( x mod I 103 , … , x mod I k ) , {\displaystyle {\begin{aligned}R/I&\to (R/I_{1})\times \cdots \times (R/I_{k})\\x{\bmod {I}}&\mapsto (x{\bmod {I}}_{1},\,\ldots ,\,x{\bmod {I}}_{k}),\end{aligned}}}

Peywendiyek di navbera zengila beşan $R/I$ û berhema rasterast a zengilan $R/I_{i},$ de heye. Di vê Çarçoveyê de, " $x{\bmod {I}}$ " wêneya Element $x$ di nav de zengila beşan a ku ji hêla îdeal $I.$ ve hatiye pênasekirin, nîşan dide. Herwiha, ger $R$ komutatîf be, hevbirîna îdealên cot-bi-cot hevpar-seretayî wekhev e bi berhema wan, ku wiha tê îfadekirin:

I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},

14∩I

I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},

∩⋯∩Ik=I52I

I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},

⋯Ik,{\displaystyle I=I_{1}\cap I_{2}\cap \cdots \cap I_{k}=I_{1}I_{2}\cdots I_{k},}

Ev Wekhevî derbasdar e ger I_i û I_j ji bo hemî i ≠ j cot-bi-cot hevpar-seretayî bin.

Şîrovekirin Di Warê Îdempotentan de

Bila $I_{1},I_{2},\dots ,I_{k}$ 10,I $I_{1},I_{2},\dots ,I_{k}$ ,…,Ik{\displaystyle I_{1},I_{2},\dots ,I_{k}} îdealên du-alî yên cot-bi-cot hevpar-seretayî bin, bi awayekî ku hevbirîna wan îdeala sifir be: $\bigcap _{i=1}^{k}I_{i}=0,$ 62kIi=80,{\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}. Ev yek nexşeyekê saz dike:

\varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})

28)×⋯×(R/Ik){\displaystyle \varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})}

Bi berçavgirtina îzomorfîzma jorîn, bila $f_{i}=(0,\ldots ,1,\ldots ,0)$ 18,…,§2728§,…,§3637§){\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)} Elementa di nav $(R/I_{1})\times \cdots \times (R/I_{k})$ 66)×⋯×(R/Ik){\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})} de nîşan bide, ku hemî pêkhate 107 ne, ji bilî pêkhateya i-yemîn, ku §111112§ ye. Herwiha, $e_{i}=\varphi ^{-1}(f_{i}).$ 138§(fi).{\displaystyle e_{i}=\varphi ^{-1}(f_{i}).} bidin nasîn.

Elementên $e_{i}$ komek îdempotentên navendî yên ku cot-cot ortogonal in pêk tînin. Bi taybetî, ev tê wateya ku $e_{i}^{2}=e_{i}$ =ei{\displaystyle e_{i}^{2}=e_{i}} (îdempotensî) û $e_{i}e_{j}=e_{j}e_{i}=0$ 100{\displaystyle e_{i}e_{j}=e_{j}e_{i}=0} (ortogonalî) ji bo hemî i û j yên cuda. Herwiha, têkiliyên jêrîn derbasdar in: ${\textstyle e_{1}+\cdots +e_{n}=1,}$ 124+⋯+en=145,{\textstyle e_{1}+\cdots +e_{n}=1,} û $I_{i}=R(1-e_{i}).$ 177−ei).{\displaystyle I_{i}=R(1-e_{i}).}

Bi kurtasî, ev Teorema Bermayî ya Çînî ya giştîkirî wekheviyekê di navbera diyarkirina îdealên du-alî yên cot-cot hevpar-seretayî yên bi qutbûnek sifir û naskirina îdempotentên navendî, cot-cot ortogonal ên ku bi hev re digihîjin 1 de datîne.

Bikaranîn

Hejmarkirina Rêzan

Teorema Bermayî ya Çînî avakirina hejmarkirinên Gödel ji bo rêzan hêsan dike, ku pêkhateyek girîng e di îspata teoremên netemamiya Gödel de.

Veguherîna Fourier a Bilez

Algorîtma FFT ya faktorên sereke, ku wekî algorîtma Good-Thomas jî tê zanîn, Teorema Bermayiya Çînî bikar tîne da ku hesibandina Veguherîna Fourier a Bilez a mezinahiya $n_{1}n_{2}$ 10 n $n_{1}n_{2}$ {\displaystyle n_{1}n_{2}} hêsan bike. Ev kêmkirin pirsgirêkê Veguherîn dike hesibandina du Veguherînên Fourier ên Bilez ên bi mezinahiyên piçûktir, bi taybetî $n_{1}$ 40 {\displaystyle n_{1}} û $n_{2}$ {\displaystyle n_{2}} , bi şertê ku $n_{1}$ 84 {\displaystyle n_{1}} û $n_{2}$ {\displaystyle n_{2}} hevjimar bin.

Şîfrekirin

Teorema Bermayiya Çînî gelek caran di piraniya pêkanînên RSA de tê bikaranîn, bi taybetî di dema pêvajoya îmzekirinê de ji bo sertîfîkayên HTTPS û di dema operasyonên Vebûna Şîfreyê de.

Herwiha, Teorema Bermayiya Çînî di şemayên parvekirina veşartî de jî tê bikaranîn. Ev yek belavkirina berhevokek parvekirinan di nav komekê de pêk tîne, ku vegerandina veşartiyek taybetî ji van parvekirinan bi awayekî kolektîf (lê ne takekesî) gengaz dike. Her parvekirinek bi hevgirtinekê re têkildar e, û veşartî bixwe ji Bişêvka Pergalê ya hevgirtinan bi karanîna Teorema Bermayiya Çînî tê derxistin. Dema ku di parvekirina veşartî de tê bikaranîn, Teorema Bermayiya Çînî Gelek caran bi rêzikên hejmarên taybetî re tê hev kirin da ku piştrast bike ku veşartî nikare ji binkomek parvekirinan ku ji hejmareke diyarkirî kêmtir e, were ji nû ve avakirin.

Çareserîya Nezelaliya Dûrahiyê

Teknîkên ji bo çareserkirina nezelaliya dûrahiyê di pergalên radarê yên bi Frekansa dubarekirina Lêdana Dil a Navgîn de dikarin wekî sepandinek taybetî ya Teorema Bermayiya Çînî werin fêm kirin.

Rizîna Surjeksiyonên Komên Abelî yên Sînorkirî

Ji bo surjeksiyonek diyarkirî $\mathbb {Z} /n\to \mathbb {Z} /m$

{\begin{aligned}\mathbb {Z} /n&\cong \mathbb {Z} /p_{n_{1}}^{a_{1}}\times \cdots \times \mathbb {Z} /p_{n_{i}}^{a_{i}}\\\mathbb {Z} /m&\cong \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}

43 a 53 × ⋯ × Z / p n i a i Z / m ≅ Z / p m 137 b 147 × ⋯ × Z / p m j b j {\displaystyle {\begin{aligned}\mathbb {Z} /n&\cong \mathbb {Z} /p_{n_{1}}^{a_{1}}\times \cdots \times \mathbb {Z} /p_{n_{i}}^{a_{i}}\\\mathbb {Z} /m&\cong \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}}

Tê zanîn ku $\{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}$ 16 , … , p m j } ⊆ { p n 58 , … , p n i } {\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}} . Herwiha, ji bo her nexşeya derxistî

\mathbb {Z} /p_{n_{k}}^{a_{k}}\to \mathbb {Z} /p_{m_{l}}^{b_{l}}

ku ji surjeksiyona destpêkê hatiye wergirtin, tê dîtin ku $a_{k}\geq b_{l}$ û $p_{n_{k}}=p_{m_{l}},$ . Ji ber ku ji bo her cotek hejmarên seretayî $p,q$ , tenê surjeksiyonên ne-sifir

\mathbb {Z} /p^{a}\to \mathbb {Z} /q^{b}

bi taybetî tenê dema ku $p=q$ û $a\geq b$ bin, têne pênasekirin.

Van çavdêriyan ji bo avakirina zengila hejmarên profînît, ku wekî sînorek berevajî ji hemî van nexşeyan tê pênasekirin, JGirîng in.

Teorema Dedekind

Teorema Dedekind serxwebûna xêzî ya karakteran destnîşan dike. Bila M monoydekê nîşan bide û k qadeke tam nîşan bide, ku di bin operasyona xwe ya pirjimariyê ya xwerû ya li ser k de wekî monoydek tê hesibandin. Wekî encam, her berhevokek sînordar ( f_i )_i∈I ji homomorfîzmayên monoyd ên cuda f_i : M → k serxwebûna xêzî nîşan dide. Ev tê wateya ku her malbatek (Alfa_i)_i∈I ji elementên Alfa_i ∈ k ku mercê jêrîn bicîh tîne:

\sum _{i\in I}\alpha _{i}f_{i}=0

39 {\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}

divê bi rastî bi malbata (0)_i∈I re têkildar be.

Îspat. Di destpêkê de, bila em bifikirin ku k qadekê pêk tîne; wekî din, qada tam k dikare bi qada beşa xwe were guhertin bêyî ku encam biguhere. Homomorfîzmayên monoyd f_i : M → k dikarin bi awayekî xêzî berfireh bibin bo homomorfîzmayên k-algebrî F_i : k[M] → k, li cihê ku k[M] zengila monoyd a M li ser k nîşan dide. Wekî encam, ji ber xêzîbûnê, merc

\sum _{i\in I}\alpha _{i}f_{i}=0,

39 , {\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0,}

paşê encam dide

\sum _{i\in I}\alpha _{i}F_{i}=0.

Herwiha, ji bo her i, j ∈ I ku i ≠ j, du nexşerêyên k-xêzî F_i : k[M] → k û F_j : k[M] → k bi hev re ne proporsiyonel in. Ger ew proporsiyonel bûna, wê demê f_i û f_j jî dê proporsiyonelî nîşan bidana, û Wekî encam dê yek bin, ji ber ku wekî homomorfîzmayên monoidê ew mercê: f_i (1) = 1 = f_j (1) bicîh tînin. Ev encam rasterast Pêşgotin a destpêkê ya cudahiya wan red dike.

Wekî encam, kernelên Ker F_i û Ker F_j bi awayekî eşkere cuda ne. Ji ber ku k[M]/Ker F_i ≅ F_i (k[M]) = k zeviyekê çêdike, ew tê wê wateyê ku Ker F_i ji bo her i Di nav de I îdealek herî mezin a k[M] pêk tîne. Ji ber cewhera wan a cuda û herî mezin, îdealên Ker F_i û Ker F_j dema ku i ≠ j ne, hevpêş in. Sepandina Teorema Bermayî ya Çînî (ku ji bo zengilên giştî derbasdar e) wê demê îzomorfîzma jêrîn saz dike:

Nexşerêya

{\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\phi (x+K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}

Li vir,

Têgeha

K=\prod _{i\in I}\mathrm {Ker} F_{i}=\bigcap _{i\in I}\mathrm {Ker} F_{i}.

Wekî encam, nexşerê wê demê wiha tê pênasekirin:

{\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\Phi (x)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}

Ev nexşandin serjê ye. Di Çarçoveya îzomorfîzman k[M]/Ker F_i → F_i (k[M]) = k de, nexşeya Φ wiha tê nîşandan:

{\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}

Dûv re,

\sum _{i\in I}\alpha _{i}F_{i}=0

39 {\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0}

dide

\sum _{i\in I}\alpha _{i}u_{i}=0

39 {\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}

ji bo her vektorek (u_i)_i∈I di nav wêneya nexşeya ψ de. Ji ber ku ψ serjê ye, ev tê wateya ku

\sum _{i\in I}\alpha _{i}u_{i}=0

39 {\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}

ji bo her vektorek

\left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k.

Wekî encam, vektora (α_i)_i∈I wekî vektora sifir (0)_i∈I ye. Q.E.D.

Covering system
Residue number system

References

Gauss, Carl Friedrich (1986), Disquisitiones Arithmeticae, wergerandin ji aliyê Clarke, Arthur A. (Çapa Duyem, serrastkirî), New York: Springer, ISBN 978-0-387-96254-2Ireland, Kenneth; Rosen, Michael (1990), Destpêkek Klasîk ji Teorîya Jimaran a Nûjen re (Çapa 2yem), Springer-Verlag, ISBN 0-387-97329-XJones, Gareth A.; Jones, J. Mary (1998). Teorîya Jimaran a Bingehîn. London; New York: Springer. ISBN 3-540-76197-7.Kak, Subhash (1986), "Aliyên Hesabkerî yên Algorîtma Aryabhata" (PDF), Kovara Hindî ya Dîroka Zanistê, §4142§ (1): 62–71Katz, Victor J. (1998), Dîrokek Matematîkê / Destpêkek (Çapa 2yem), Addison Wesley Longman, ISBN 978-0-321-01618-8Libbrecht, Ulrich (1973), Matematîka Çînî di Sedsala Sêzdemîn de: "Shu-shu Chiu-chang" a Ch'in Chiu-shao, Dover Publications Inc, ISBN 978-0-486-44619-6Ore, Øystein (1952), "Teorîya Bermayî ya Çînî ya Giştî," Mehnameya Matematîkî ya Amerîkî, §6061§ (6): 365–370, doi:10.2307/2306804, JSTOR 2306804, MR 0048481Ore, Oystein (1988) [1948], Teorîya Jimaran û Dîroka Wê, Dover, ISBN 978-0-486-65620-5Pisano, Leonardo (2002), Fibonacci's Liber Abaci, wergerandin ji aliyê Sigler, Laurence E., Springer-Verlag, r. 402–403, ISBN 0-387-95419-8Rosen, Kenneth H. (1993), Teorîya Jimaran a Bingehîn û Serlêdanên Wê (Çapa 3yem), Addison-Wesley, ISBN 978-0201-57889-8Sengupta, Ambar N. (2012), Nûnertiya Komên Sînorkirî: Destpêkek Nîv-hêsan, Springer, ISBN 978-1-4614-1232-8Bourbaki, N. (1989), Cebîr I, Springer, ISBN 3-540-64243-9
Nivîsa tevahî ya Sun-tzu Suan-ching (Çînî) – Projeya Nivîsa Çînî

Teorema Bermahiyê ya Çînî (Chinese remainder theorem)