Ĉina restteoremo estas la nomo de multaj similaj teoremoj de abstrakta algebro kaj nombroteorio.
Simultana kongrueco de entjeroj estas sistemo de linearaj kongruecoj
![{\displaystyle {\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}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/8a1e9cf49eed56a8e99aabc95fea6e5a4090c1c6)
por kiu estas trovendaj ĉiuj
, kiuj solvas ĉiujn kongruecojn samtempe. Se solvo
ekzistas kaj oni difinas
("pmko" signifas la plej malgrandan komunan oblon), la aro
enhavas ĉiujn solvojn. Sed ankaŭ eblas, ke neniu solvo ekzistas.
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 reciproke primaj. Ĝi tekstas:
estu popare reciproke primaj entjeroj. Tiam por ĉiu entjera opo
ekzistas entjero
, kiu solvas la jenan simultanan kongruecon:
kun ![{\displaystyle i=1,2,\ldots ,n}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/b4139aedce69fd9e24a74aefdf330009777ee2fb)
Ĉiuj solvoj por tiu kongrueco estas kongrua module
.
Tiu produto
egalas al la PMKO kaŭze de reciproka primeco.
Trovado de unu solvo
Unu solvo
povas esti trovita jene: Por ĉiu
la nombroj
kaj
estas reciproke primaj, do oni povas trovi du nombrojn
kaj
, ekzemple kun la etendita eŭklida algoritmo, kun la propreco
.
Se oni metas
, tiam validas
![{\displaystyle e_{i}\equiv 1{\pmod {m_{i}}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/424a584d74defdb97274077c79a4c140d9e8388c)
.
Tiam la nombro
![{\displaystyle x:=\sum _{i=1}^{n}a_{i}e_{i}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/7d64ed1500c5a5a14b1deb28c570360db229a1b0)
estas solvo por la simultana kongrueco.
Ekzemplo
Estu serĉata entjero
, por kiu validas jeno:
![{\displaystyle {\begin{matrix}x&\equiv &2{\pmod {3}}\\x&\equiv &3{\pmod {4}}\\x&\equiv &2{\pmod {5}}\\\end{matrix}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/d19edd7f88fc28b2affb34a6ae943ee183377aea)
Ĉi tie validas
.
Kun helpo de etendita eŭklida algoritmo oni kalkulas
, do ![{\displaystyle e_{1}=-20}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/f683178ae2c5f67b77aefd7178efeb2e9d607379)
, do ![{\displaystyle e_{2}=-15}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/540f1de632e528fe2a970f72401699b387cc7bb3)
, do ![{\displaystyle e_{3}=-24}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/52c4beadb12af2a8989c4384c182092096d34644)
Tiam unu solvo estas
. Kaŭze de
ĉiuj aliaj solvoj estas kongruaj al 47 module 60.
Ankaŭ ĉe la kazo, ke la moduloj ne estas reciproke primaj, ekzistas solvo kelkfoje. La ekzakta kondiĉo tekstas:
Solvo por la simultana kongrueco ekzistas strikte tiam, se por ĉiuj
validas:
.
Ĉiuj solvoj estas kongruaj module la PMKO de
.
En la kazo, ke solvo ekzistas, unu simultana kongrueco povas esti solvita, ekzemple, per substituoj, paŝo post paŝo, ankaŭ se la moduloj ne estas reciproke primaj.
Ekzemplo
La celo de unu klassika enigmo estas trovi la malplej grandan naturalan nombron, kiu havas la reston 1 ĉe dividado kun resto per 2, 3, 4, 5 kaj 6, kaj estas nete dividebla per 7. Do oni serĉas la malplej grandan pozitivan solvon
de la simultana kongrueco.
![{\displaystyle {\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}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/b0c7da65bd5f43792ce6ad4236eb2c79b59da104)
Ĉar la moduloj ne estas reciproke primaj, oni ne povas apliki la ĉinan restteoremon senpere.
Sed oni povas kunigi la unuan kvin kondiĉojn al
, kiu signifas, ke solvo estu trovita por
![{\displaystyle {\begin{matrix}x&\equiv &1&{\pmod {60}}\\x&\equiv &0&{\pmod {7}}\\\end{matrix}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/5fcd746b0941207f7aa70d3833d296ca4928b734)
Tiu sistemo de kongruecoj nun solveblas pere de la ĉina restteoremo.
La jenaj ambaŭ kongruecoj estu donita:
![{\displaystyle {\begin{matrix}x&\equiv &a&{\pmod {n}}\\x&\equiv &b&{\pmod {m}}\\\end{matrix}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/17d51f93c43bf7f9367b60a9344c12dd8d04a754)
Se tiuj solveblas, do
, ili estas ekvivalenta je la simpla kongrueco:
![{\displaystyle {\begin{matrix}x&\equiv &a-yn{\frac {a-b}{d}}&{\pmod {\frac {nm}{d}}}\\\end{matrix}}}](http://178.128.105.246/cars-https-wikimedia.org/api/rest_v1/media/math/render/svg/3df5e64f20b3d7c5f356c66974b5b58594b6bc39)
kun
.
Tio funkcias ankaŭ kiam la nombroj n kaj m ne estas reciproke primaj; tio do estas klara simpligo por solvi simultanajn kongruecojn.
Sistemo de kongruecoj povas esti solvita per refarita aplikado de tiu simpligo.