Kineski teorem o ostatcima

Kineski teorem o ostatcima (eng. Chinese Remainder Theorem – CRT) govori o rješenju sustava linearnih kongruencija.

Za ovaj se teorem veže ime kineskog matematičara Sun Tzua. Smatra se da je teorem tada korišten u kineskoj vojsci za prebrojavanje vojnika. Ipak, u potpunosti ga je iskazao tek 1247. godine Kinez Qin Jiushao.

Moderni iskaz teorema glasi ovako. Neka su $m_{1},m_{2},...,m_{r}$ u parovima relativno prosti brojevi te neka su $a_{1},a_{2},...,a_{r}\in \mathbb {Z} .$ Tada sustav kongruencija $x\equiv a_{1}{\pmod {m_{1}}},...,x\equiv a_{r}{\pmod {m_{r}}}$ ima rješenja.

Uz to, ako je $x_{0}$ jedno rješenje sustava, onda su sva rješenja tog sustava dana s $x\equiv x_{0}{\pmod {m_{1}m_{2}\cdot ...\cdot m_{r}}}$.

Dokaz

Neka je $m=m_{1}m_{2}\cdot ...\cdot m_{r}$ te neka je $n_{j}={\frac {m}{m_{j}}}$ za $j=1,2,...,r.$ Zbog uvjeta da su $m_{1},m_{2},...,m_{r}$ u provima relativno prosti, imamo da je $M(m_{j},n_{j})=1$ pa postoji $x_{j}\in \mathbb {Z}$ takav da je $n_{j}x_{j}\equiv a_{j}{\pmod {m_{j}}}.$

Promotrimo sada broj $x_{0}=n_{1}x_{1}+...+n_{r}x_{r}.$

Za njega vrijedi $x_{0}=0+0+n_{j}x_{j}+0+...+0\equiv a_{j}{\pmod {m_{j}}}.$ Zato je $x_{0}$ rješenje sustava kongruencija s kojim smo počeli.

Konačno, ako su $x,x_{0}$ dva rješenja tog sustava, onda je $x\equiv x_{0}{\pmod {m_{1}}}$ za $j=1,2,...,r$. Zbog toga što su $m_{j}$ u parovima relativno prosti, dobivamo da je $x\equiv x_{0}{\pmod {m}}.$