Ogled vira Kitajski izrek o ostankih

[[File:Sun_Tzu_Chinese_remainder_theorem.svg|thumb|Sun čijeva izvorna predstavitev: {{nowrap|''x'' &equiv; 2 (mod 3)}} {{nowrap|&equiv; 3 (mod 5)}} {{nowrap|&equiv; 2 (mod 7)}} {{nowrap|z rešitvami}} {{nowrap|''x'' <nowiki>=</nowiki> 23 + 105''k'',}} {{nowrap|kjer ''k'' &isin; ℤ}}]]

'''Kitajski izrek o ostankih''' govori o [[kongruenca]]h v [[teorija števil|teoriji števil]] in njihovih posplošitvah v [[asbtraktna algebra|abstraktni algebri]]. Prvič ga je brez [[matematični dokaz|dokaza]] objavil kitajski matematik [[Sun Či]] (Sun-tzu) v 5. stoletju v svojem delu ''[[Sun Čijeva klasična matematika]]''.

V osnovni obliki kitajski izrek o ostankih določa takšno število ''n'', da, če ga delimo z danimi [[delitelj]]i, bodo pri [[deljenje|deljenju]] ostali dani ostanki.

Katero je na primer najmanjše število ''n'', da, kadar ga delimo s 3, da ostanek 2, kadar ga delimo s 5, da ostanek 3, in kadar ga delimo s 7, da ostanek 2? Običajni uvodni zgled je ženska, ki pove policaju, da je izgubila svojo košaro z jajci. Če je iz nje na enkrat vzela ven 3 jajca, sta v košari ostali 2 jajci, če jih je vzela ven 5, jih je ostalo 3, in, če jih je vzela ven 7, sta ostali 2. Kakšno je najmanjše število jajc v košari? Odgovor na oba problema je 23. Vse rešitve pa imajo obliko 23 + 105''k'' za poljubna [[nenegativno število|nenegativna]] [[celo število|cela števila]] ''k'' ≥ 0. Problem lahko opišemo s splošnim sistemom enačb:

: <math> n = ax + r_{1} = by + r_{2} = cz + r_{3} \!\, , </math>

oziroma posebej:

: <math> n = 3x+2 = 5y+3 = 7z+2 \!\, . </math>
==Izrek==
Naj bodo ''n''<sub>1</sub>, ..., ''n''<sub>''k''</sub> naravna števila večja od 1, ki se pogosto imenujejo ''[[modularna aritmetika|moduli]]'' ali ''[[Evklidsko deljenje|delitelji]]''. Naj bo ''N'' produkt vseh ''n''<sub>''i''</sub>.

Če so si ''n''<sub>''i''</sub> med sabo [[tuje število|tuji]] in če so ''a''<sub>1</sub>, ..., ''a''<sub>''k''</sub> cela števila, kjer velja 0 ≤ ''a''<sub>''i''</sub> < ''n''<sub>''i''</sub> za vsak ''i'', nam kitajski izrek o ostankih pove, da obstaja eno in samo eno celo število ''x'', da velja 0 ≤ ''x'' < ''N'' in da je ostanek [[evklidsko deljenje|evklidskega deljenja]] ''x'' z ''n''<sub>''i''</sub> enak ''a''<sub>''i''</sub> za vsak ''i''.

To se lahko drugače pove v obliki [[kongruenca|kongruenc]]:
Če so si vsi ''n''<sub>''i''</sub> med sabo tuji in če so ''a''<sub>1</sub>, ..., ''a''<sub>''k''</sub> katerakoli cela števila, potem obstaja tako celo število ''x'', da velja

:<math>\begin{align}
 x &\equiv a_1  \pmod{n_1} \\
  &\,\,\,\vdots \\
 x &\equiv a_k \pmod{n_k},
\end{align}</math>
in katerikoli dve rešitvi, recimo ''x''<sub>1</sub> in ''x''<sub>2</sub>, sta kongruentni v modulu ''N'', torej {{math|''x''<sub>1</sub> ≡ ''x''<sub>2</sub> (mod ''N'')}}.<ref>{{harvnb|Ireland|Rosen|1990|page=34}}</ref>

V [[abstraktna algebra|abstraktni algebri]] se izrek po navadi navede kot: če so si vsi ''n''<sub>''i''</sub> med sabo tuji, potem preslikava
:<math>x \bmod N \;\mapsto\;(x \bmod n_1,\, \ldots,\, x \bmod n_k)</math>
definira [[izomorfizem kolobarja]]<ref>{{harvnb|Ireland|Rosen|1990|page=35}}</ref>

:<math>\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}</math>
med [[kolobar (matematika)|kolobarji]] [[cela števila modula n|celih števil modula ''N'']] in [[direktni produkt]] kolobarjev celih števil ''n''<sub>''i''</sub>. To pomeni, da se lahko pri izdelavi zaporedja aritmetičnih operacij v <math>\mathbb{Z}/N\mathbb{Z}</math> uporabi tudi izračun neodvisno v vsakem <math>\mathbb{Z}/n_i\mathbb{Z}</math> in se potem dobi rezultat z dodajanjem izomorfizma (od desne proti levi). To je lahko veliko hitreje kot direktni izračun, če so ''N'' in število operacij velike. To se pogosto uporablja pod izrazom ''večmodularni izračun'' za [[Linearna algebra|linearno algebro]] nad celimi števili ali [[Racionalno število|racionalnimi števili]].

Izrek obstaja tudi v jeziku [[kombinatorika|kombinatorike]] kot dejstvo, da neskončna [[aritmetično zaporedje|aritmetična zaporedja]] celih števil oblikujejo [[Hellyjeva družina|Hellyjevo družino]].<ref>{{harvnb|Duchet|1995}}</ref>

==Dokaz==
Obstoj in unikatnost rešitve se lahko dokaže neodvisno. Toda prvi dokaz obstoja, ki je podan spodaj, to unikatnost uporablja.

===Unikatnost===
Naj bosta tako {{mvar|x}} in tako {{mvar|y}} rešitvi vsem kongruencam. Ker {{mvar|x}} in {{mvar|y}} pri deljenju z {{math|''n<sub>i</sub>''}} podata enak ostanek, je njuna razlika {{math|''x'' − ''y''}} večkratnik vsakega {{math|''n<sub>i</sub>''}}. Ker so si vsi {{math|''n<sub>i</sub>''}} med sabo tuji, njihov produkt {{math|''N''}} deli tudi {{math|''x'' − ''y''}} in torej sta {{mvar|x}} in {{mvar|y}} kongruentna v modulu {{math|''N''}}. Če smo predpostavili, da sta {{mvar|x}} in {{mvar|y}} nenegativna in manj kot {{math|''N''}} (kot v prvi trditvi izreka), je njuna razlika lahko tudi večkratnik od {{math|''N''}} natanko takrat, ko je {{math|1=''x'' = ''y''}}.

===Obstoj (prvi dokaz)===
Preslikava
:<math>x \bmod N \mapsto (x \bmod n_1, \ldots, x\bmod n_k)</math>
slika kongruenčne razrede modula {{math|''N''}} v zaporedja kongruenčnih razredov modula {{math|''n<sub>i</sub>''}}. Dokaz unikatnosti pokaže, da je ta preslikava [[injektivnost|injektivna]]. Ker imata [[domena funkcije|domena]] in [[kodomena]] te preslikave enako število elementov, je preslikava tudi [[surjektivnost|surjektivna]], kar dokaže obstoj te rešitve.

Ta dokaz je zelo preprost, toda ne ponudi nobenega načina za izračun rešitve. Ne more se tudi posplošiti na ostale situacije, toda drugi dokazi pa se lahko.

===Obstoj (konstruktivni dokaz)===
Obstoj se lahko dobi z eksplicitno konstrukcijo {{mvar|x}}.<ref>{{harvnb|Rosen|1993|page=136}}</ref> To konstrukcijo se lahko razdeli na dva koraka: najprej se reši problem na primeru dveh modulov, nato pa se ga z [[matematična indukcija|indukcijo]] razširi na katerokoli število modulov.

====Primer dveh modulov====
Želimo rešiti sistem:
:<math>
\begin{align}
  x &\equiv a_1 \pmod {n_1}\\
  x &\equiv a_2 \pmod {n_2},
\end{align}
</math>
kjer sta si <math>n_1</math> in <math>n_2</math> tuji.

[[Bézoutova identiteta]] nam poda obstoj dveh celih števil <math>m_1</math> in <math>m_2</math>, da velja 
:<math>m_1n_1+m_2n_2=1.</math>
Celi števili <math>m_1</math> in <math>m_2</math> se lahko izračuna z [[razširjeni evklidov algoritem|razširjenim evklidovim algoritmom]].

Rešitev je podana s
:<math>x = a_1m_2n_2+a_2m_1n_1.</math>
Torej, 
:<math>\begin{align}
x&=a_1m_2n_2+a_2m_1n_1\\
&=a_1(1 - m_1n_1) + a_2m_1n_1 \\
&=a_1 + (a_2 - a_1)m_1n_1,
\end{align}</math>
Iz tega sledi, da <math>x \equiv a_1 \pmod {n_1}.</math> Druga kongruenca se dokaže podobno.

====Splošni primer====
Naj bo zaporedje kongruenčnih enačb:
:<math>
\begin{align} 
  x &\equiv a_1 \pmod{n_1} \\ 
  &\vdots              \\ 
  x &\equiv a_k \pmod{n_k},
\end{align}
</math>
kjer so si <math>n_i</math> med sabo tuji. Prvi dve enačbi imata rešitev <math>a_{1,2}</math> po prejšnjem dokazu. Množica rešitev prvih dveh enačb je množica vseh rešitev enačbe
:<math>x \equiv a_{1,2} \pmod{n_1n_2}.</math>

Ker so ostali <math>n_i</math> tuji z <math>n_1n_2,</math>, se to zmanjša iz reševanja {{mvar|k}} enačb na podoben primer reševanja <math>k-1</math> enačb. Če ta postopek ponavljamo, na koncu dobimo rešitev začetnega problema.

===Obstoj (direktna konstrukcija)===
Za konstrukcijo rešitve, ni nujno, da naredimo indukcijo na številih modulov. Toda takšna direktna konstrukcija obravnava več izračunov pri velikih številih, kar jo naredi manj učinkovito in manj uporabljeno. Toda [[Lagrangova interpolacija]] je poseben primer te konstrukcije, ki se namesto na cela števila nanaša na polinome.

Naj bo <math>N_i = N/n_i</math> produkt vseh modulov, razen ena. Ker so si <math>n_i</math> med sabo tuji, sta si tuja tudi <math>N_i</math> in <math>n_i</math>. [[Bézoutova identiteta]] pove, da obstajata celi števili <math>M_i</math> in <math>m_i</math>, da velja
:<math>M_iN_i + m_in_i=1.</math>

Rešitev sistema kongruenc je
:<math>x=\sum_{i=1}^k a_iM_iN_i.</math>
Ker je <math>N_j</math> večkratnik od <math>n_i</math>, če <math>i\neq j</math>,
dobimo
:<math>x \equiv a_iM_iN_i \equiv a_i(1-m_in_i) \equiv a_i \pmod{n_i}, </math>
za vsak <math>i</math>.

== Zunanje povezave ==

* Hazewinkel, Michiel, urednik (2001), »[http://www.encyclopediaofmath.org/index.php/Chinese_remainder_theorem Chinese remainder theorem]«, ''[[Encyclopedia of Mathematics]]'', [[Springer Science+Business Media|Springer]], ISBN 978-1-55608-010-4 {{ikona en}}
* {{MathWorld|id=ChineseRemainderTheorem|title=Chinese Remainder Theorem}}

{{normativna kontrola}}

[[Kategorija:Modularna aritmetika]]
[[Kategorija:Abstraktna algebra]]
[[Kategorija:Kitajska matematika]]
[[Kategorija:Izreki teorije števil]]