[Algorithm][WIP] 중국인의 나머지 정리 (Chinese Remainder Theorem)

서론

중국인의 나머지 정리(Chinese remainder theorem; CRT)는 중국의 5세기 문헌인 『손자산경(孫子算經)』에는 나오는 문제로, 내용은 다음과 같다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가? 

 

x = r1 (mod n1)

x = r2 (mod n2)

...

x = rk (mod nk) 이고 N = n1 * n2 * ... * nk 라고 하자.

 

mi는 mi * (N/ni) = 1(mod ni)를 계산해서 구한다. 

 

일반해는 x = m1 (N/n1) + m2 (N/n2) + ... + mk (N/nk) mod N

 

배경 지식

곱셈의 역원 구하기

 

출처

https://namu.wiki/w/중국인의%20나머지%20정리