중국인의 나머지 정리
중국의 5세기 문헌인 손자산경(孫子算經)에 나오는 문제로, 내용은 다음과 같다.
3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?
이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 중국인의 나머지 정리가 되었다고 한다.
\(m_1, m_2, \cdots, m_n\)이 쌍마다 서로소 즉, \(\gcd\left(m_i,m_j\right)=1,i\neq j\)이면, 다음 연립 합동식
$$x\equiv a_{i}\left ( \bmod\;m_{i} \right )\;\;\;\;\;\;\;\;i=1,2,3,4 \cdots n$$
를 만족하는 \(x\)는 \(\bmod \;(n_1 n_2 \cdots n_k)\)에서 유일하게 존재한다는 정리이다.
위의 경우를 만족하는 유일한 해 \(x\)는
\(x \equiv a_1M_1N_1 + a_2M_2N_2 + \cdots + a_kM_kN_k\;(\bmod \; M)\)
이렇게 구할수 있는데 여기서
\(M=n_1 n_2 \cdots n_k\)
\(M_i=M/n_i\)
\(N_i \equiv M_i ^ {-1} \; (\bmod \; n_i)\)이다.
예제로 \(x \equiv 2\;(\bmod \; 3),\;x \equiv 3\;(\bmod \; 5),\;x \equiv 2\;(\bmod \; 7)\)를 만족하는 \(x\)를 구해보자.
위의 공식에서 사용되는 변수 \(M, M_i, N_i\)를 먼저 구해보면
\(M = 3 \times 5 \times 7 = 105\)
\(M_1 = M / 3 = 35,\;M_2 = M / 5 = 21,\;M_3 = M / 7 = 15\)
\(N_1 \equiv M_1^{-1}\equiv 2\;(\bmod\;3)\)
\(N_2 \equiv M_2^{-1}\equiv 1\;(\bmod\;5)\)
\(N_3 \equiv M_3^{-1}\equiv 1\;(\bmod\;7)\)이다.
사용된 변수를 모두 계산했으니 위 공식대로 대입해보면
\(x \equiv 2M_1N_1 + 3M_2N_2 + 2M_3N_3\;(\bmod\;M)\)
\(\equiv 2\cdot 35\cdot 2 + 3\cdot 21\cdot 1 + 2\cdot 15\cdot 1\;(\bmod\;105)\)
\(\equiv 23\;(\bmod\;105)\)
라는 해를 구할 수 있다.
증명
증명은 존재성과 유일성 두 가지로 나뉘는데 증명하기 앞서 알아두어야 할 정리부터 증명하고 시작하겠음
양의 정수 \(m\)과 \(a_1,a_2,\cdots,a_n\)에 대하여 \(m\)이 \(a1,a2,⋯,a_n\)와 각각 서로소이면,
\(m\)과 \(a_1a_2\cdots a_n\)은 서로소이다.
\(m\)과 \(a1,a2,⋯,a_n\)이 서로소가 아니라고 가정하면 \(m\)과 \(a_1a_2\cdots a_n\)의 공약수인 소수 \(p\)가 존재한다. \(p\mid a_1a_2\cdots a_n\)이므로 \(p\mid a_i\)가 존재한다.
그러면 \(p\)는 \(a_i\)와 \(m\)를 모두 나누므로 가정에 모순된다.
양의 정수 \(m\)과 \(a_1,a_2,\cdots,a_n\)에 대하여 \(m\)이 \(a_1,a_2,\cdots,a_n\) 의 각각의 배수이면 \(m\)은 \(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)\)의 배수이다.
나눗셈 정리에 의하여 \(m=q\cdot\text{lcm}\left(a_1,a_2,\cdots,a_n\right)+r\)을 만족하는 정수 \(q,r\)이 유일하게 존재한다\((0\leq r<\text{lcm}\left(a_1,a_2,\cdots,a_n\right))\).
그런데 \(a_i\)가 \(m\)과 \(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)\)을 모두 나누므로 \(a_i\)는 \(r\)도 나눠야 한다.
이것은 모든 \(i\)에 대해 참이므로 \(r\)은 \(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)\)보다 작은 \(a_i\)들의 공배수이다.
이걸 만족하는 값은 \(r=0\)밖에 없으며, 이는 곧 \(m\)이 \(\text{lcm}\left(a_1,a_2,\cdots,a_n\right)\)의 배수이다.
존재성
\(m=m _1m_2⋯m_n\)라고 하자. 또, \(n_k=\frac{m}{m_k}\)라고 놓자. 즉, \(n_k\)는 \(m_k\)를 제외한 나머지 \(m_i\)들의 곱을 의미한다.
도움정리 1로부터 \(\gcd\left(n_k,m_k\right)=1\)이다. 그럼 베주 항등식에 의해,
\(s_k n_k + t_k m_k =1\)을 만족하는 정수 \(s_k,t_k\)가 존재한다. 이를 합동식 형태로 고치면,
\(s_k n_k\equiv1\left(\bmod\,m_k\right)\)이다.
이제 \(x = a_1 n_1 s_1 + a_2 n_2 s_2 + \cdots + a_n n_n s_n\)라고 놓자. \(j \neq k\)이면 \(m_k\mid n_j\)이고, 따라서
\(x\equiv a_k n_k s_k \equiv a_k \cdot 1 = a_k\left(\bmod\,m_k\right)\)이다.(\(1<=k<=n\)인 임의의 자연수)
즉, \(x\)는 주어진 연립 합동식의 한 해이다.
유일성
\(x,\;y\)가 주어진 연립 합동식의 해라고 하자. 그러면,
\(x\equiv a_1\left(\text{mod}\,m_1\right),\;y\equiv a_1\left(\text{mod}\,m_1\right)\)
\(x\equiv a_2\left(\text{mod}\,m_2\right),\;y\equiv a_2\left(\text{mod}\,m_2\right)\)
\(x\equiv a_n\left(\text{mod}\,m_n\right),\;y\equiv a_n\left(\text{mod}\,m_n\right)\)이다.
그러므로, 임의의 \(k\,\left(1\leq k\leq n\right)\)에 대하여, \(x\equiv a_k\equiv y\left(\text{mod}\,m_k\right)\)이고, 그래서 \(x-y\equiv0\left(\text{mod}\,m_k\right)\)이다.
즉, \(x-y\)는 모든 \(m_k\)들의 배수이다. 따라서 도움정리 2에 의해, \(\text{lcm}\left(m_1,m_2,\cdots,m_n\right)\mid\left(x-y\right)\)이다.
그런데 \(m_1,m_2,\cdots,m_n\)들이 쌍마다 서로소이므로 \(m_1 m_2 \cdots m_n\mid\left(x-y\right)\)이다.
즉, \(x\equiv y\left(\text{mod}\,m_1 m_2 \cdots m_n\right)\)이고
이는 주어진 연립 합동식의 해가 유일함을 보인다.