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 [math]\displaystyle{ m_1, m_2, ..., m_r }[/math] u parovima relativno prosti brojevi te neka su [math]\displaystyle{ a_1, a_2, ..., a_r \in \mathbb{Z}. }[/math] Tada sustav kongruencija [math]\displaystyle{ x \equiv a_1 \pmod {m_1}, ..., x \equiv a_r \pmod {m_r} }[/math] ima rješenja.

Uz to, ako je [math]\displaystyle{ x_0 }[/math] jedno rješenje sustava, onda su sva rješenja tog sustava dana s [math]\displaystyle{ x \equiv x_0 \pmod {m_1m_2 \cdot ... \cdot m_r} }[/math].

Dokaz

Neka je [math]\displaystyle{ m = m_1m_2 \cdot ... \cdot m_r }[/math] te neka je [math]\displaystyle{ n_j = \frac{m}{m_j} }[/math] za [math]\displaystyle{ j = 1, 2, ..., r. }[/math] Zbog uvjeta da su [math]\displaystyle{ m_1, m_2, ..., m_r }[/math] u provima relativno prosti, imamo da je [math]\displaystyle{ M(m_j, n_j) = 1 }[/math] pa postoji [math]\displaystyle{ x_j \in \mathbb{Z} }[/math] takav da je [math]\displaystyle{ n_jx_j \equiv a_j \pmod {m_j}. }[/math]

Promotrimo sada broj [math]\displaystyle{ x_0 = n_1x_1 + ... + n_rx_r. }[/math]

Za njega vrijedi [math]\displaystyle{ x_0 = 0 + 0 + n_jx_j + 0 + ... + 0 \equiv a_j \pmod {m_j}. }[/math] Zato je [math]\displaystyle{ x_0 }[/math] rješenje sustava kongruencija s kojim smo počeli.

Konačno, ako su [math]\displaystyle{ x, x_0 }[/math] dva rješenja tog sustava, onda je [math]\displaystyle{ x \equiv x_0 \pmod {m_1} }[/math] za [math]\displaystyle{ j = 1, 2, ..., r }[/math]. Zbog toga što su [math]\displaystyle{ m_j }[/math] u parovima relativno prosti, dobivamo da je [math]\displaystyle{ x \equiv x_0 \pmod {m}. }[/math]