Kineski teorem o ostatcima: razlika između inačica

Izvor: Hrvatska internetska enciklopedija
Prijeđi na navigaciju Prijeđi na pretraživanje
Bot: Automatski unos stranica
 
m bnz
 
Redak 1: Redak 1:
<!--'''Kineski teorem o ostatcima'''-->'''Kineski teorem o ostatcima''' ([[Engleski jezik|eng.]] ''Chinese Remainder Theorem'' – CRT) govori o rješenju sustava linearnih [[Modularna aritmetika|kongruencija]].
Kineski teorem o ostatcima''' ([[Engleski jezik|eng.]] ''Chinese Remainder Theorem'' – CRT) govori o rješenju sustava linearnih [[Modularna aritmetika|kongruencija]].


Za ovaj se teorem veže ime [[Kina|kineskog]] [[Matematika|matematičara]] Sun Tzua. Smatra se da je teorem tada korišten u kineskoj [[Vojska|vojsci]] za prebrojavanje vojnika. Ipak, u potpunosti ga je iskazao tek 1247. godine [[Kinezi|Kinez]] Qin Jiushao.<ref>
Za ovaj se teorem veže ime [[Kina|kineskog]] [[Matematika|matematičara]] Sun Tzua. Smatra se da je teorem tada korišten u kineskoj [[Vojska|vojsci]] za prebrojavanje vojnika. Ipak, u potpunosti ga je iskazao tek 1247. godine [[Kinezi|Kinez]] Qin Jiushao.<ref>

Posljednja izmjena od 18. ožujak 2022. u 20:47

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

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

  1. ↑ https://www.britannica.com/science/Chinese-remainder-theorem
  2. ↑ Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.