Det kinesiske restteoremet

Dette innlegget har allerede blitt vist 3177 ganger!

Det kinesiske restteoremet handler om å løse et likningssystem som består av flere kongruenslikninger med forskjellig modulus. For å løse det må vi definere noen ting først.

Definisjon: La a,c og m være heltall med m > 0. Hvis ac ≡ 1 (mod) m sier vi at c er en invers til a modulo m.

Definisjon: La n1, n2, … nr være r heltall. Disse tallene er relativt primiske hvis ni er relativt primisk til nj for alle i ≠ j

Teorem: Dersom modulusene m1, m2, … , mr er parvis relativt primiske, la M = m1*m2*m3*…*mr. Da har følgende system en entydig løsning modulo M

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)

x ≡ ar (mod mr)

For å finne løsningen av systemet gjør vi følgende for hver i ∈ {1,2,…,r}: Setter Mi = M/mi og ki = inversen til Mi modulo mi. Da er løsningen gitt slik:

x ≡ summen av ai*Mi*ki for alle i fra 1 til r  (mod M)