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 = a x + r_{1} = b y + r_{2} = c z + r_{3},

oziroma posebej:

n = 3 x + 2 = 5 y + 3 = 7 z + 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{matrix} x & \equiv a_{1} (\mod n_{1}) \\ ⋮ \\ x & \equiv a_{k} (\mod n_{k}), \end{matrix}

in katerikoli dve rešitvi, recimo x₁ in x₂, sta kongruentni v modulu N, torej Predloga:Math.^[1]

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

x mod N \mapsto (x {mod n}_{1}, \dots, x {mod n}_{k})

definira izomorfizem kolobarja^[2]

ℤ / N ℤ ≅ ℤ / n_{1} ℤ \times \dots \times ℤ / n_{k} ℤ

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 $ℤ / N ℤ$ uporabi tudi izračun neodvisno v vsakem $ℤ / n_{i} ℤ$ 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 Predloga:Mvar in tako Predloga:Mvar rešitvi vsem kongruencam. Ker Predloga:Mvar in Predloga:Mvar pri deljenju z Predloga:Math podata enak ostanek, je njuna razlika Predloga:Math večkratnik vsakega Predloga:Math. Ker so si vsi Predloga:Math med sabo tuji, njihov produkt Predloga:Math deli tudi Predloga:Math in torej sta Predloga:Mvar in Predloga:Mvar kongruentna v modulu Predloga:Math. Če smo predpostavili, da sta Predloga:Mvar in Predloga:Mvar nenegativna in manj kot Predloga:Math (kot v prvi trditvi izreka), je njuna razlika lahko tudi večkratnik od Predloga:Math natanko takrat, ko je Predloga:Math.

Obstoj (prvi dokaz)

Preslikava

x mod N \mapsto (x {mod n}_{1}, \dots, x {mod n}_{k})

slika kongruenčne razrede modula Predloga:Math v zaporedja kongruenčnih razredov modula Predloga:Math. 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 Predloga:Mvar.^[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{matrix} x & \equiv a_{1} (\mod n_{1}) \\ x & \equiv a_{2} (\mod n_{2}), \end{matrix}

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

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

Splošni primer

Naj bo zaporedje kongruenčnih enačb:

\begin{matrix} x & \equiv a_{1} (\mod n_{1}) \\ ⋮ \\ x & \equiv a_{k} (\mod n_{k}), \end{matrix}

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} (\mod n_{1} n_{2}) .

Ker so ostali $n_{i}$ tuji z $n_{1} n_{2},$ , se to zmanjša iz reševanja Predloga:Mvar 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

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

Rešitev sistema kongruenc je

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

Ker je $N_{j}$ večkratnik od $n_{i}$ , če $i \neq j$ , dobimo

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

za vsak $i$ .

Zunanje povezave

Hazewinkel, Michiel, urednik (2001), »Chinese remainder theorem«, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 Predloga:Ikona en
Predloga:MathWorld

Predloga:Normativna kontrola

[1] Predloga:Harvnb

[2] Predloga:Harvnb

[3] Predloga:Harvnb

[4] Predloga:Harvnb

[1]

[2]

[3]

[4]

Kitajski izrek o ostankih

Vsebina

Izrek

Dokaz

Unikatnost

Obstoj (prvi dokaz)

Obstoj (konstruktivni dokaz)

Primer dveh modulov

Splošni primer

Obstoj (direktna konstrukcija)

Zunanje povezave

Navigacijski meni

Kitajski izrek o ostankih

Izrek

Dokaz

Unikatnost

Obstoj (prvi dokaz)

Obstoj (konstruktivni dokaz)

Primer dveh modulov

Splošni primer

Obstoj (direktna konstrukcija)

Zunanje povezave

Navigacijski meni

Iskanje