중국인의 나머지 정리

역사 raw
대문 랜덤 문서 최근 토론
분류
1. 개요2. 증명
2.1. 도움정리 12.2. 도움정리 22.3. 도움정리 32.4. 존재성2.5. 유일성
3. 문제를 푸는 방법4. 결론5. 관련 문서


Chinese Remainder Theorem

1. 개요[편집]

중국의 5세기 문헌인 『손자산경(孫子算經)』[1][2]에는 다음과 같은 문제가 있다고 한다.
3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가? [3]
이를 기리기 위해 이런 종류의 문제의 일반적인 해법은 중국인의 나머지 정리가 되었다고 한다. 위 문제는 뭔가 초등학교 문제집에나 나올 법한 느낌이지만[4] 실은 연립 합동식 문제로, 정수론과 관련된 내용이다. 초등학생들이 못 푸는 게 당연한 것. 중국인의 나머지 정리는 이와 같은 연립 합동식의 해의 존재성과 유일성을 증명하는 정리이다.

아래 정리를 읽기 전에, 정신이 안드로메다로 가는 듯한 느낌(...)을 받지 않기 위해선 반드시 합동식 문서를 읽고 오자. mod에 대해 간단히 설명하자면, A(mod B)A\left(\text{mod}\,B\right)면 BB로 나누어 AA의 나머지를 생기게 하는 수라는 뜻이다. C=A(mod B)C=A\left(\text{mod}\,B\right)라면 일반적인 방정식으로는 C=Bk+AC=Bk+A, (0≤A<B,k∈0\leq A<B, k\inℤ)로 나타난다.

자세한 정리는 다음과 같다.
m1,m2,⋯ ,mnm_1,m_2,\cdots,m_n이 쌍마다 서로 소(즉, gcd⁡(mi,mj)=1,i≠j\gcd\left(m_i,m_j\right)=1,i\neq j)이면, 다음 연립 합동식
x≡a1(mod m1)x\equiv a_1\left(\text{mod}\,m_1\right)
x≡a2(mod m2)x\equiv a_2\left(\text{mod}\,m_2\right)
x≡a3(mod m3)x\equiv a_3\left(\text{mod}\,m_3\right)
⋮\vdots
x≡an(mod mn)x\equiv a_n\left(\text{mod}\,m_n\right)
은 법 m1m2⋯mnm_1 m_2\cdots m_n에 대하여 유일한 해를 갖는다.

2. 증명[편집]

증명은 크게 존재성, 유일성 두 가지로 나뉜다. 또한 이 정리를 증명하기에 앞서 도움정리를 알아두어야 한다.

2.1. 도움정리 1[편집]

양의 정수 mm과 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n에 대하여 mm이 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n와 각각 서로소이면, mm과 a1a2⋯ana_1a_2\cdots a_n은 서로소이다.
증명
서로소가 아니라고 가정하자. 그럼 mm과 a1a2⋯ana_1a_2\cdots a_n의 공약수인 소수 pp가 존재한다. p∣a1a2⋯anp\mid a_1a_2\cdots a_n이므로 p∣aip\mid a_i인 aia_i가 존재한다. 그러면 pp는 aia_i와 mm을 모두 나누고, 이는 가정에 모순이다.

2.2. 도움정리 2[편집]

양의 정수 mm과 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n에 대하여 mm이 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n의 각각의 배수이면 mm은 lcm(a1,a2,⋯ ,an)\text{lcm}\left(a_1,a_2,\cdots,a_n\right)의 배수이다.
증명
나눗셈 정리에 의하여 m=q⋅lcm(a1,a2,⋯ ,an)+rm=q\cdot\text{lcm}\left(a_1,a_2,\cdots,a_n\right)+r 을 만족하는 정수 q,rq,r이 유일하게 존재한다 (0≤r≤lcm(a1,a2,⋯ ,an)0\leq r\leq\text{lcm}\left(a_1,a_2,\cdots,a_n\right)). 그런데 aia_i가 mm과 lcm(a1,a2,⋯ ,an)\text{lcm}\left(a_1,a_2,\cdots,a_n\right)을 모두 나누므로 aia_i는 rr도 나눠야 한다. 이것은 모든 ii에 대해 참이므로 rr은 lcm(a1,a2,⋯ ,an)\text{lcm}\left(a_1,a_2,\cdots,a_n\right)보다 작은 aia_i들의 공배수이다. 이걸 만족하는 값은 r=0r=0밖에 없으며, 이는 곧 mm이 lcm(a1,a2,⋯ ,an)\text{lcm}\left(a_1,a_2,\cdots,a_n\right)의 배수임을 보인다.

2.3. 도움정리 3[편집]

양의 정수 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n에 대하여 gcd⁡(ai,aj)=1,i≠j\gcd\left(a_i,a_j\right)=1,i\neq j(즉, 쌍마다 서로 소(pairwise relatively prime))이면,
lcm(a1,a2,⋯ ,an)=a1a2⋯an\text{lcm}\left(a_1,a_2,\cdots,a_n\right)=a_1 a_2 \cdots a_n이 성립한다.
이에 대한 증명은 최소공배수 참조. 사실 증명이라 할 것도 없다.

2.4. 존재성[편집]

m=m1m2⋯mnm=m_1 m_2 \cdots m_n라고 하자. 또, nk=mmkn_k=\frac{m}{m_k}라고 놓자. 즉, nkn_k는 mkm_k를 제외한 나머지 mim_i들의 곱을 의미한다.
도움정리 1로부터 gcd⁡(nk,mk)=1\gcd\left(n_k,m_k\right)=1이다. 그럼 베주 항등식에 의해,
sknk+tkmk=1s_k n_k + t_k m_k =1
을 만족하는 정수 sk,tks_k,t_k가 존재한다. 이를 합동식 형태로 고치면,
sknk≡1(mod mk)s_k n_k\equiv1\left(\text{mod}\,m_k\right)
이다. 이제
x=a1n1s1+a2n2s2+⋯+annnsnx = a_1 n_1 s_1 + a_2 n_2 s_2 + \cdots + a_n n_n s_n
라고 놓자. j≠kj\neq k이면 mk∣njm_k\mid n_j이고,[5] 따라서
x≡aknksk≡ak⋅1=ak(mod mk)x\equiv a_k n_k s_k \equiv a_k \cdot 1 = a_k\left(\text{mod}\,m_k\right) 이다.(1<=k<=n인 임의의 자연수)[6][7]
즉, xx는 주어진 연립 합동식의 한 해이다.

2.5. 유일성[편집]

x,yx,y가 주어진 연립 합동식의 해라고 하자.[8]그러면,
x≡a1(mod m1)x\equiv a_1\left(\text{mod}\,m_1\right), y≡a1(mod m1)y\equiv a_1\left(\text{mod}\,m_1\right)
x≡a2(mod m2)x\equiv a_2\left(\text{mod}\,m_2\right), y≡a2(mod m2)y\equiv a_2\left(\text{mod}\,m_2\right)
⋮\vdots
x≡an(mod mn)x\equiv a_n\left(\text{mod}\,m_n\right), y≡an(mod mn)y\equiv a_n\left(\text{mod}\,m_n\right)
이다. 그러므로, 임의의 k (1≤k≤n)k\,\left(1\leq k\leq n\right)에 대하여, x≡ak≡y(mod mk)x\equiv a_k\equiv y\left(\text{mod}\,m_k\right)이고, 그래서 x−y≡0(mod mk)x-y\equiv0\left(\text{mod}\,m_k\right)이다.[9] 즉, x−yx-y는 모든 mkm_k들의 배수이다. 따라서 도움정리 2에 의해,
lcm(m1,m2,⋯ ,mn)∣(x−y)\text{lcm}\left(m_1,m_2,\cdots,m_n\right)\mid\left(x-y\right)
이다. 그런데, m1,m2,⋯ ,mnm_1,m_2,\cdots,m_n들이 쌍마다 서로 소이므로, 도움정리 3으로부터
m1m2⋯mn∣(x−y)m_1 m_2 \cdots m_n\mid\left(x-y\right)이다. 즉,
x≡y(mod m1m2⋯mn) x\equiv y\left(\text{mod}\,m_1 m_2 \cdots m_n\right)이고, 이는 주어진 연립 합동식의 해가 유일함을 보인다.

3. 문제를 푸는 방법[편집]

위의 문제를 풀어보도록 하자. 방법은 해의 존재성을 증명하는 것과 비슷하다.

3, 5, 7이 쌍마다 서로소이므로 주어진 연립 합동식은 3×5×7=1053\times5\times7=105에 대하여 유일한 해를 가진다. m=105,n1=35,n2=21,n3=15m=105,n_1=35,n_2=21,n_3=15라 하자.
n1s1≡35s1≡2s1≡1(mod 3)n_1 s_1\equiv35s_1\equiv2s_1\equiv1\left(\text{mod}\,3\right)
n2s2≡21s2≡s2≡1(mod 5)n_2 s_2\equiv21s_2\equiv s_2\equiv1\left(\text{mod}\,5\right)
n3s3≡15s3≡s3≡1(mod 7)n_3s_3\equiv15s_3\equiv s_3\equiv1\left(\text{mod}\,7\right)
을 풀면 s1=2,s2=1,s3=1s_1=2,s_2=1,s_3=1가 해임을 알 수 있다.[10] 그러므로 x≡a1n1s1+a2n2s2+a3n3s3≡2⋅35⋅2+3⋅21⋅1+2⋅15⋅1≡233≡23(mod 105)x \equiv a_1 n_1 s_1 + a_2 n_2 s_2 + a_3n_3s_3 \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \equiv 233 \equiv 23 \left(\text{mod}\,105\right)이다.

따라서 x≡23(mod 105)x\equiv23\left(\text{mod}\,105\right)가 주어진 연립 합동식의 해이다.

4. 결론[편집]

풀어서 말하면 서로소인 nn개의 수 각각에 대해 일정한 나머지를 만족하는 수는 그들 nn개의 최소공배수에 일정한 나머지를 더한 값으로 나타난다는 정리이다. 사실 어떤 자연수 AA에 대해 일정한 나머지 BB를 가지는 수에 AA의 배수를 더하면 이 또한 AA로 나눈 나머지가 BB이므로, 존재성과 유일성을 증명하고 나면 nn개 수의 최소공배수마다 조건을 만족하는 수가 반복되어 나타난다는 것은 쉽게 유추가 가능하다.

5. 관련 문서[편집]

[1] 여기에서의 '손자(孫子)'는 『손자병법』을 쓴 그 '손자'와 한자는 같지만 그보다 훨씬 후대의 인물이다.[2] 중국의 옛 수학서에는 이 『손자산경(孫子算經)』 외에도, 『주비산경(周髀算經)』, 『구장산술(九章算術)』, 『해도산경(海島算經)』, 『오조산경(五曹算經)』, 『하후양산경(夏侯陽算經)』, 『장구건산경(張邱建算經)』, 『오경산술(五經算術)』, 『집고산경(緝古算經)』, 『철술(綴術)』 등이 있다. 이들을 통틀어 '산경십서(算經十書)'로 칭한다.[3] 풀이는 아래쪽 문단 참조. 답은 23, 128 등등이다.[4] 그런데 그것이 실제로 일어났습니다 의외로 초등학교 문제집에 이런 문제들이 나오고, 심지어 중학교 방정식 단원에 나오는 경우도 있다.[5] nkn_k의 정의 때문에 성립[6] 나머지 ajnjsja_j n_j s_j는 mkm_k로 나누면 나머지가 0 이므로 j=kj=k인 경우만 생각해 주면 된다.[7] 또한 nkskn_k s_k는 위 sknk≡1(mod mk)s_k n_k\equiv 1\left(\text{mod}\,m_k\right)와 합동식의 성질 때문에 1로 바뀐다.[8] 임의의 두 답이 같음을 보이는 방법은 유일성을 증명하는 데 자주 쓰이는 테크닉이다.[9] 추이율. 합동식의 성질 참조[10] 여러 값 중 아무거나 고르면 된다.