Kitajski izrek o ostankih

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
Sun čijeva izvorna predstavitev: x ≡ 2 (mod 3) ≡ 3 (mod 5) ≡ 2 (mod 7) z rešitvami x = 23 + 105k, kjer k ∈ ℤ

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:

oziroma posebej:

Izrek[uredi | uredi kodo]

Naj bodo n1, ..., nk naravna števila večja od 1, ki se pogosto imenujejo moduli ali delitelji. Naj bo N produkt vseh ni.

Če so si ni med sabo tuji in če so a1, ..., ak cela števila, kjer velja 0 ≤ ai < ni za vsak i, nam kitajski izrek o ostankih nam pove, da obstaja eno in samo eno celo število x, da velja 0 ≤ x < N in da je ostanek evklidskega deljenja x z ni enak ai za vsak i.

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

in katerikoli dve rešitvi, recimo x1 in x2, sta kongruentni v modulu N, torej x1x2 (mod N).[1]

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

definira izomorfizem kolobarja[2]

med kolobarji celih števil modula N in direktni produkt kolobarjev celih števil ni. To pomeni, da se lahko pri izdelavi zaporedja aritmetičnih operacij v uporabi tudi izračun neodvisno v vsakem 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[uredi | uredi kodo]

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

Unikatnost[uredi | uredi kodo]

Naj bosta tako x in tako y rešitvi vsem kongruencam. Ker x in y pri deljenju z ni podata enak ostanek, je njuna razlika xy večkratnik vsakega ni. Ker so si vsi ni med sabo tuji, njihov produkt N deli tudi xy 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)[uredi | uredi kodo]

Preslikava

slika kongruenčne razrede modula N v zaporedja kongruenčnih razredov modula ni. 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)[uredi | uredi kodo]

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[uredi | uredi kodo]

Želimo rešiti sistem:

kjer sta si in tuji.

Bézoutova identiteta nam poda obstoj dveh celih števil in , da velja

Celi števili in se lahko izračuna z razširjenim evklidovim algoritmom.

Rešitev je podana s

Torej,

Iz tega sledi, da Druga kongruenca se dokaže podobno.

Splošni primer[uredi | uredi kodo]

Naj bo zaporedje kongruenčnih enačb:

kjer so si med sabo tuji. Prvi dve enačbi imata rešitev po prejšnjem dokazu. Množica rešitev prvih dveh enačb je množica vseh rešitev enačbe

Ker so ostali tuji z , se to zmanjša iz reševanja k enačb na podoben primer reševanja enačb. Če ta postopek ponavljamo, na koncu dobimo rešitev začetnega problema.

Obstoj (direktna konstrukcija)[uredi | uredi kodo]

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 produkt vseh modulov, razen ena. Ker so si med sabo tuji, sta si tuja tudi in . Bézoutova identiteta pove, da obstajata celi števili in , da velja

Rešitev sistema kongruenc je

Ker je večkratnik od , če , dobimo

za vsak .

Zunanje povezave[uredi | uredi kodo]

  • Hazewinkel, Michiel, urednik (2001), »Chinese remainder theorem«, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 (angleško)
  • Weisstein, Eric Wolfgang. "Chinese Remainder Theorem". MathWorld (angleščina).
  1. Ireland & Rosen 1990, str. 34
  2. Ireland & Rosen 1990, str. 35
  3. Duchet 1995
  4. Rosen 1993, str. 136