중국인의 나머지 정리(Chinese Remainder Theorem) 기본 이해하기

1. 중국인의 나머지 정리(Chinese Remainder Theorem) 정수 $m_{1}, m_{2}, ..., m_{n}$이 임의의 i,j = 1,2,...,n에 대하여 $i \neq j$일때, $m_{i}$와 $m_{j}$가 서로소라면, 즉 $$gcd(m_{i}, m_{j}) = 1, i \neq j$$ 라고 하자. 일차연립합동식 $$x \equiv a_{1} (mod m_{1})$$ , $$x \equiv a_{2} (mod m_{2})$$ , $$x \equiv a_{3} (mod m_{3})$$ , $$\vdots$$ , $$x \equiv a_{n} (mod m_{n})$$ 의 해는 mod $m_{1}, m_{2}, ..., m_{n}$에 대하여 유일하게 존재한다. 2. 보조정리 1 정수 a,b,k..