Chinese Remainder Theorem(중국인 나머지 정리)

중국인 나머지 정리

• m1, m2, …, mr이 양의 정수이면서 서로소일 때, 임의의 정수 a1, a2, …,ar에 대하여 다음 r 개의 합동식 x ≡ ai (mod mi) (i=1,2,…,r)을 만족하는 정수 x가 존재

예시

• x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7)을 만족하는 x?
  1. M = m1 x m2 x m3 = 3 x 5 x 7 = 105
  2. M1= M/m1 = 105/3 = 35, M2= M/m2 = 105/5 = 21, M3= 105/7 = 15
  3. y1: M1 ∙ y1 ≡ 1 (mod m1) ⇒ 35y1 ≡ 1 (mod 3) ⇒ 2y1 ≡ 1 (mod 3) ⇒ y1 ≡ 2 (mod 3)
  4. y2: M2 ∙ y2 ≡ 1 (mod m2) ⇒ 21y2 ≡ 1 (mod 5) ⇒ y2 ≡ 1 (mod 5)
  5. y3: M3 ∙ y3 ≡ 1 (mod m3) ⇒ 15y3 ≡ 1 (mod 7) ⇒ y3 ≡ 1 (mod 7)
  6. x = (a1 ∙ M1 ∙ y1) + (a2 ∙ M2 ∙ y2) + (a2 ∙ M2 ∙ y2) = 1∙35∙2 + 2∙21∙1 +3∙15∙1 = 157
  7. x ≡ 157 (mod 105) ⇒ x ≡ 52 (mod 105)

서로소가 아닐 때

• m1, m2, …, mr이 서로소가 아니라면?
  • x ≡ 5 (mod 6) - 식(1), x ≡ 3 (mod 10) - 식(2), x ≡ 8 (mod 15) - 식(3)
    1. 식(1) ⇒ x = 6t + 5 - 식(4)
    2. 식(4) & 식(2) ⇒ 6t + 5 ≡ 3 (mod 10) ⇒ 6t ≡ 8 (mod 10) ⇒ 3t ≡ 4 (mod 5) ⇒(확장된 유클리드 알고리즘 이용) t ≡ 3 (mod 5) 즉, t = 5s + 3 - 식(5)
    • 확장된 유클리드 알고리즘 이용하면 t = …, 8, 13, …
  1. 식(4) & 식(5) ⇒ x = 6(5s + 3) + 5 ⇒ x = 30s + 23 - 식(6)
  2. 식(6) & 식(3) ⇒ 30s+ 23 ≡ 8 (mod 15) ⇒ 30s ≡ 0 (mod 15) ⇒ 2s ≡ 0 (mod 1) ⇒ s = 0 (mod 1) ⇒ s = 모든 정수 - 식 (7)
  3. 식(7) & 식(6) ⇒ x = 30v + 23 ⇒ x ≡ 23 (mod 30)

코드

중국인의 나머지 정리