Prijeđi na sadržaj

Kineski teorem o ostatcima

Izvor: Wikipedija

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 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

[uredi | uredi kôd]

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 [2]

Izvori

[uredi | uredi kôd]
  1. Chinese remainder theorem
  2. Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.