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.^[1]

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 ℤ .$ Tada sustav kongruencija $x \equiv a_{1} (\mod m_{1}), . . ., x \equiv a_{r} (\mod 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} (\mod 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 ℤ$ takav da je $n_{j} x_{j} \equiv a_{j} (\mod 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} (\mod 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} (\mod m_{1})$ za $j = 1, 2, . . ., r$ . Zbog toga što su $m_{j}$ u parovima relativno prosti, dobivamo da je $x \equiv x_{0} (\mod m) .$ ^[2]

Izvori

Predložak:Izvori

↑ Chinese remainder theorem
↑ Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.

[1] Chinese remainder theorem

[2] Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.

[1]

[2]

Kineski teorem o ostatcima

Dokaz

Izvori

Navigacijski izbornik

Traži