알고리즘이나 정수론, 암호학을 공부하면 항상 등장하는 개념인 중국인의 나머지 정리에 대해 알아볼 것이다.중국인의 나머지 정리란?중국인의 나머지 정리는 다음과 같은 여러 선형 합동식을 만족하는 유일한 해를 구할 수 있게 해주는 강력한 정리이다.$$x \equiv 1\; \mathrm{(mod \; 3)},\\ x \equiv 2 \; \mathrm{(mod \; 5)},\\ x \equiv 3 \; \mathrm{(mod \; 7)}$$합동식들의 $a \equiv b \mod m$의 형태에서, 모든 m들은 서로 서로소 관계여야 한다.또한 각 합동식에서 x의 계수가 1이 아닌 경우가 있는데, 그런 경우에는 확장된 유클리드 알고리즘(EEA)를 사용해서 곱셈 역원을 구해서 양변에 곱해준 후 CRT를 적용한다.중..