중국인의 나머지 정리(Chinese Remainder Theorem, CRT) 계산 방법

Chinese Remainder Theorem (중국인의 나머지 정리)를 이용하여
x ≡ 1 ( mod 5 ) { x를 5로 나눈 나머지는 1 }
x ≡ 2 ( mod 6 ) { x를 6로 나눈 나머지는 2 }
x ≡ 3 ( mod 7 ) { x를 7로 나눈 나머지는 3 }
의 해를 구하는 과정.

• step 0: 주어진 mod 값 5, 6, 7 을 나란히 적는다.
• step 1: 주어진 나머지 값 1, 2, 3 을 나란히 적는다.
• step 2: 5와 각 mod에 대한 5의 잉여역원을 나머지의 앞,뒤로 곱해준다.(mod 가 5인 열 제외)
• step 3: 6과 각 mod에 대한 6의 잉여역원을 나머지의 앞,뒤로 곱해준다.(mod 가 6인 열 제외)
• step 4: 7과 각 mod에 대한 7의 잉여역원을 나머지의 앞,뒤로 곱해준다.(mod 가 7인 열 제외)
• (=>각 mod 에 대해 나머지 값을 유지하면서 다른 mod 에 대한 나머지는 0이 되도록 만드는 과정이다.)
• step 4-a: 현재 단계에서 각각의 곱을 계산하여 더해도 답을 구할 수 있다.
• step 5-a: 계산을 간단히 하기 위해 두개의 곱을 각 mod 에 대한 나머지값만 구한다.
• step 5-b: 위 과정을 반복하되, 각 mod 의 곱에 대해서는 나머지를 구하지 않고 유지한다.
• step 5-c: 각각의 곱을 계산하면 step 4-a 보다 작은 숫자가 나와 계산이 더 간단하다.
• (=>5-b에서 나머지를 구할 때 음수값을 잘 이용하면 숫자가 더 작아진다. ex) mod 7에서 6*5*5 -> 6*5*-2)
  

다른 예 step 5 의 과정을 통해 계산이 더 간단해졌다.
mod 11에서 11*7*4 를 11*7*-1로 계산하면 숫자가 더 작아진다.