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.Chinese remainder theorem Britannica. Pristupljeno 21. studenoga 2025.
Moderni iskaz teorema glasi ovako. Neka su u parovima relativno prosti brojevi te neka su Tada sustav kongruencija ima rješenja.
Uz to, ako je jedno rješenje sustava, onda su sva rješenja tog sustava dana s .
Dokaz Neka je te neka je za Zbog uvjeta da su u provima relativno prosti, imamo da je pa postoji takav da je
Promotrimo sada broj
Za njega vrijedi Zato je rješenje sustava kongruencija s kojim smo počeli.
Konačno, ako su dva rješenja tog sustava, onda je za . Zbog toga što su u parovima relativno prosti, dobivamo da je Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
Izvori
Kategorija:Matematika