Ĉina restteoremo

Ĉina restteoremo estas la nomo de multaj similaj teoremoj de abstrakta algebro kaj nombroteorio.

Simultanaj kongruecoj de entjeroj

Simultana kongrueco de entjeroj estas sistemo de linearaj kongruecoj

${\begin{matrix}x&\equiv &a_{1}&{\pmod {m_{1}}}\\x&\equiv &a_{2}&{\pmod {m_{2}}}\\&\vdots &&\\x&\equiv &a_{n}&{\pmod {m_{n}}}\\\end{matrix}}$${\begin{matrix}x&\equiv &a_{1}&{\pmod {m_{1}}}\\x&\equiv &a_{2}&{\pmod {m_{2}}}\\&\vdots &&\\x&\equiv &a_{n}&{\pmod {m_{n}}}\\\end{matrix}}$

por kiu ĉuij $x$$x$ estu trovita, kiuj solvas ĉiujn kongruecojn samtempe. Se solvo $x$$x$ ekzistas kaj oni definas $M:=\operatorname {pmko} \{m_{1},m_{2},\ldots ,m_{n}\}$$M:=\operatorname {pmko} \{m_{1},m_{2},\ldots ,m_{n}\}$ ("pmko" signifas la plej malgrandan komunan oblon), la aro $\{x+k\cdot M\mid k\in \mathbb {Z} \}$$\{x+k\cdot M\mid k\in \mathbb {Z} \}$ enhavas ĉiujn solvojn. Sed ankaŭ eblas, ke nenio solvo ekzistas.

Interprimaj moduloj

La origina versio de la restteoremo (el la libro La kompendio de aritmetiko de Sūn Zǐ de la ĉina matematikisto Sūn Zǐ) deklaras eldiron pri simultanajn kongruecojn en la kazo, ke la moduloj estas interprimaj. Ĝi tekstas:

$m_{1},m_{2},\ldots ,m_{n}$$m_{1},m_{2},\ldots ,m_{n}$ estu pare interprimaj entjeroj. Tiam por ĉiu entjera opo $a_{1},a_{2},\ldots ,a_{n}$$a_{1},a_{2},\ldots ,a_{n}$ ekzistas entjero $x$$x$, kiu solvas la jenan simultanan kongruecon:

$x\equiv a_{i}{\pmod {m_{i}}}$$x\equiv a_{i}{\pmod {m_{i}}}$ kun $i=1,2,\ldots ,n$$i=1,2,\ldots ,n$

Ĉiuj solvoj por tiu kongrueco estas kongrua module $M:=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n}$$M:=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{n}$.

Tio Produkto $M$$M$ egalas la PMKO kaŭze de interprimeco.

Trovado de unu solvo

Unu solvo $x$$x$ povas esti trovita jen: Por ĉiu $i$$i$ la nombroj $m_{i}$$m_{i}$ kaj $M_{i}:={\tfrac {M}{m_{i}}}$$M_{i}:={\tfrac {M}{m_{i}}}$ estas interprimoj, do oni povas trovi du nombrojn $r_{i}$$r_{i}$ kaj $s_{i}$$s_{i}$, ekzemple kun la etendita eŭklida algoritmo, kun la propreco

$r_{i}\cdot m_{i}+s_{i}\cdot M_{i}=1$$r_{i}\cdot m_{i}+s_{i}\cdot M_{i}=1$.

Se oni metas $e_{i}:=s_{i}\cdot M_{i}$$e_{i}:=s_{i}\cdot M_{i}$, tiam validas

$e_{i}\equiv 1{\pmod {m_{i}}}$$e_{i}\equiv 1{\pmod {m_{i}}}$

$e_{i}\equiv 0{\pmod {m_{j}}},\ j\neq i$$e_{i}\equiv 0{\pmod {m_{j}}},\ j\neq i$.

Tiam la nombro

$x:=\sum _{i=1}^{n}a_{i}e_{i}$$x:=\sum _{i=1}^{n}a_{i}e_{i}$

estas solvo por la simultana kongrueco.

Ekzemplo

Estu serĉata entjero $x$$x$ kun la propreco

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&\equiv &3{\pmod {4}}\\x&\equiv &2{\pmod {5}}\\\end{matrix}}$${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&\equiv &3{\pmod {4}}\\x&\equiv &2{\pmod {5}}\\\end{matrix}}$

Ĉi tie validas $M=3\cdot 4\cdot 5=60,\ M_{1}={\tfrac {M}{3}}=20,\ M_{2}={\tfrac {M}{4}}=15,\ M_{3}={\tfrac {M}{5}}=12$$M=3\cdot 4\cdot 5=60,\ M_{1}={\tfrac {M}{3}}=20,\ M_{2}={\tfrac {M}{4}}=15,\ M_{3}={\tfrac {M}{5}}=12$. Kun helpo de etendita eŭklida algoritmo oni kalkulas

$7\cdot 3+(-1)\cdot 20=1$$7\cdot 3+(-1)\cdot 20=1$, do $e_{1}=-20$$e_{1}=-20$

$4\cdot 4+(-1)\cdot 15=1$$4\cdot 4+(-1)\cdot 15=1$, do $e_{2}=-15$$e_{2}=-15$

$5\cdot 5+(-2)\cdot 12=1$$5\cdot 5+(-2)\cdot 12=1$, do $e_{3}=-24$$e_{3}=-24$

Tiam unu solvo estas $x=2\cdot (-20)+3\cdot (-15)+2\cdot (-24)=-133$$x=2\cdot (-20)+3\cdot (-15)+2\cdot (-24)=-133$. Kaŭze de $-133\equiv 47{\pmod {60}}$$-133\equiv 47{\pmod {60}}$ ĉiuj aliaj solvoj estas kongruaj al 47 module 60.

Ĝenerala kazo

Ankaŭ ĉe la kazo, ke la moduloj ne estas interprimaj, ekzistas solvo kelkfoje. La ekzakta kondiĉo tekstas: Solvo por la simultana kongrueco ekzistas strikte tiam, se por ĉiuj $i\neq j$$i\neq j$ validas:

$a_{i}\equiv a_{j}{\pmod {\operatorname {pgkd} (m_{i},m_{j})}}$$a_{i}\equiv a_{j}{\pmod {\operatorname {pgkd} (m_{i},m_{j})}}$.

Ĉiuj solvoj estas kongruaj module la PMKO de $m_{i}$$m_{i}$.

En la kazo, ke solvo ekzistas, unu simultana kongrueco povas esti solvita ekzemple per iom post iom substituo, ankaŭ se la moduloj ne estas interprimoj.

Ekzemplo

La celo de unu klassika enigmo estas trovi la malplej grandan naturalan nombron, kiu ĵetas la reston 1 ĉe dividado kun resto kun 2, 3, 4, 5 kaj 6, kaj estas dividebla kun 7. Do oni serĉas la malplej grandan pozitivan solvon $x$$x$ de la simultana kongrueco.

${\begin{matrix}x&\equiv &1&{\pmod {2}}\\x&\equiv &1&{\pmod {3}}\\x&\equiv &1&{\pmod {4}}\\x&\equiv &1&{\pmod {5}}\\x&\equiv &1&{\pmod {6}}\\x&\equiv &0&{\pmod {7}}\\\end{matrix}}$${\begin{matrix}x&\equiv &1&{\pmod {2}}\\x&\equiv &1&{\pmod {3}}\\x&\equiv &1&{\pmod {4}}\\x&\equiv &1&{\pmod {5}}\\x&\equiv &1&{\pmod {6}}\\x&\equiv &0&{\pmod {7}}\\\end{matrix}}$

Ĉar la moduloj ne estas interprimaj, oni ne povas apliki la ĉinan restteoremon senpere. Sed oni povas kunigi la unuan kvin kondiĉojn al $x\equiv 1{\pmod {\operatorname {pgkd} \{2,3,4,5,6\}}}$$x\equiv 1{\pmod {\operatorname {pgkd} \{2,3,4,5,6\}}}$, kiu signifas, ke solvo estu trovita por

${\begin{matrix}x&\equiv &1&{\pmod {60}}\\x&\equiv &0&{\pmod {7}}\\\end{matrix}}$${\begin{matrix}x&\equiv &1&{\pmod {60}}\\x&\equiv &0&{\pmod {7}}\\\end{matrix}}$

Tiu sistemo de kongruecoj nun solveblas kun la ĉina restteoremo.

Rekta solvado de simultanaj kongruecoj de entjeroj

La jenaj ambaŭ kongruecoj estu donita:

${\begin{matrix}x&\equiv &a&{\pmod {n}}\\x&\equiv &b&{\pmod {m}}\\\end{matrix}}$${\begin{matrix}x&\equiv &a&{\pmod {n}}\\x&\equiv &b&{\pmod {m}}\\\end{matrix}}$

Se tiuj solveblas, do $a\equiv b{\pmod {d}}$$a\equiv b{\pmod {d}}$, ili estas ekvivalenta je la simpla kongrueco:

${\begin{matrix}x&\equiv &a-yn{\frac {a-b}{d}}&{\pmod {\frac {nm}{d}}}\\\end{matrix}}$${\begin{matrix}x&\equiv &a-yn{\frac {a-b}{d}}&{\pmod {\frac {nm}{d}}}\\\end{matrix}}$

kun $d=\operatorname {pgkd} (n,m)=yn+zm$$d=\operatorname {pgkd} (n,m)=yn+zm$.

Tio ankaŭ funkcias kun neinterprimaj nombroj n kaj m kaj do aperas kiel klara simpligo por solvi simultanajn kongruecojn. Sistemo de kongruecoj povas esti solvita per refarita aplikado de tiu simpligo.