Kitajski izrek o ostankih

Kitajski izrek o ostankih govori o kongruencah v teoriji števil in njihovih posplošitvah v abstraktni algebri. Prvič ga je brez 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 delitelji, bodo pri 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 + 105k za poljubna nenegativna cela števila k ≥ 0. Problem lahko opišemo s splošnim sistemom enačb:

n=ax+r_{1}=by+r_{2}=cz+r_{3}\!\,,

oziroma posebej:

n=3x+2=5y+3=7z+2\!\,.

Izrek

Naj bodo n₁, ..., n_k naravna števila večja od 1, ki se pogosto imenujejo moduli ali delitelji. Naj bo N produkt vseh n_i.

Če so si n_i med sabo tuji in če so a₁, ..., a_k cela števila, kjer velja 0 ≤ a_i < n_i 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 evklidskega deljenja x z n_i enak a_i za vsak i.

To se lahko drugače pove v obliki kongruenc: Če so si vsi n_i med sabo tuji in če so a₁, ..., a_k katerakoli cela števila, potem obstaja tako celo število x, da velja

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

in katerikoli dve rešitvi, recimo x₁ in x₂, sta kongruentni v modulu N, torej $x 1 \equiv x 2 (mod N)$ .^[1]

V abstraktni algebri se izrek po navadi navede kot: če so si vsi n_i med sabo tuji, potem preslikava

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

definira izomorfizem kolobarja^[2]

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

med kolobarji celih števil modula N in direktni produkt kolobarjev celih števil n_i. To pomeni, da se lahko pri izdelavi zaporedja aritmetičnih operacij v $\mathbb {Z} /N\mathbb {Z}$ uporabi tudi izračun neodvisno v vsakem $\mathbb {Z} /n_{i}\mathbb {Z}$ 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 linearno algebro nad celimi števili ali racionalnimi števili.

Izrek obstaja tudi v jeziku kombinatorike kot dejstvo, da neskončna aritmetična zaporedja celih števil oblikujejo Hellyjevo družino.^[3]

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 $x$ in tako $y$ rešitvi vsem kongruencam. Ker $x$ in $y$ pri deljenju z $n i$ podata enak ostanek, je njuna razlika $x - y$ večkratnik vsakega $n i$ . Ker so si vsi $n i$ med sabo tuji, njihov produkt $N$ deli tudi $x - y$ in torej sta $x$ in $y$ kongruentna v modulu $N$ . Če smo predpostavili, da sta $x$ in $y$ nenegativna in manj kot $N$ (kot v prvi trditvi izreka), je njuna razlika lahko tudi večkratnik od $N$ natanko takrat, ko je $x = y$ .

Obstoj (prvi dokaz)

Preslikava

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

slika kongruenčne razrede modula $N$ v zaporedja kongruenčnih razredov modula $n i$ . Dokaz unikatnosti pokaže, da je ta preslikava injektivna. Ker imata domena in kodomena te preslikave enako število elementov, je preslikava tudi 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 $x$ .^[4] To konstrukcijo se lahko razdeli na dva koraka: najprej se reši problem na primeru dveh modulov, nato pa se ga z indukcijo razširi na katerokoli število modulov.

Primer dveh modulov

Želimo rešiti sistem:

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

kjer sta si $n_{1}$ in $n_{2}$ tuji.

Bézoutova identiteta nam poda obstoj dveh celih števil $m_{1}$ in $m_{2}$ , da velja

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

Celi števili $m_{1}$ in $m_{2}$ se lahko izračuna z razširjenim evklidovim algoritmom.

Rešitev je podana s

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

Torej,

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

Iz tega sledi, da $x\equiv a_{1}{\pmod {n_{1}}}.$ Druga kongruenca se dokaže podobno.

Splošni primer

Naj bo zaporedje kongruenčnih enačb:

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

kjer so si $n_{i}$ med sabo tuji. Prvi dve enačbi imata rešitev $a_{1,2}$ po prejšnjem dokazu. Množica rešitev prvih dveh enačb je množica vseh rešitev enačbe

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

Ker so ostali $n_{i}$ tuji z $n_{1}n_{2},$ , se to zmanjša iz reševanja $k$ enačb na podoben primer reševanja $k-1$ 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 $N_{i}=N/n_{i}$ produkt vseh modulov, razen ena. Ker so si $n_{i}$ med sabo tuji, sta si tuja tudi $N_{i}$ in $n_{i}$ . Bézoutova identiteta pove, da obstajata celi števili $M_{i}$ in $m_{i}$ , da velja