경고 : 최신판이 아닙니다. 이 문서의 오래된 판을 편집하고 있습니다. 이것을 저장하면, 이 판 이후로 바뀐 모든 편집이 사라집니다. 로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요!'''중국인의 나머지 정리'''(Chinese Remainder Theorem, CRT)란, [[정수론]]과 추상대수학에 관한 정리이다. 정수론에서는 연립[[합동식]]의 해를 구하는 방법이라 생각하면 된다. [[정수론]] 내용이 다 그렇듯이 대학교에 가서나 배우게 되지만, 수학 경시대회를 준비한다면 알아놔야 한다. 정확히 말하면 연립합동식을 푸는 방법만 알면 되지만... 이름이 왜 하필 '''중국인'''의 나머지 정리냐 하면, 5세기의 중국 수학서 손자산경에 연립합동식 문제가 처음 등장했기 때문. 그 문제는 다음과 같다.<ref>[[위키백과:중국인의 나머지 정리 #역사]]를 참조</ref> {{인용문|개수를 알지 못하는 것들이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 질문: 총 몇 개인가?|《孫子算經》 하권(下卷) 문제 26번}} 위 문제는 <math>\begin{cases} x\equiv2\pmod3\\x\equiv3\pmod5\\x\equiv2\pmod7\end{cases}</math>와 동치이다. 자세한 풀이는 아래쪽 문단의 예시를 참조. == 정수론에서 == 정수론에서의 중국인의 나머지 정리는 다음과 같다. :<math>m_1,m_2,\cdots,m_n</math>이 쌍마다 서로소이면, 다음 연립 합동식 <math>\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\quad\vdots\\x\equiv a_n\pmod{m_n}\end{cases}</math>은 법 <math>m_1m_2\cdots m_n</math>에 대하여 유일한 해를 갖는다. 증명은 크게 존재성과 유일성으로 나뉘며, 본 증명 전에 도움정리를 먼저 증명한다. === 도움정리 1 === 양의 정수 <math>m</math>과 <math>a_1,a_2,\cdots,a_n</math>에 대해, <math>m</math>이 <math>a_1,a_2,\cdots,a_n</math>와 각각 [[서로소]]면, <math>m</math>과 <math>a_1a_2\cdots a_n</math>도 서로소이다. 증명 :서로소가 아니라고 가정하자. 그럼 <math>m</math>과 <math>a_1a_2\cdots a_n</math>의 [[소수]]인 [[공약수]] <math>p</math>가 존재한다. 그럼 <math>p\mid a_1a_2\cdots a_n</math>이므로, 적당한 <math>i</math>에 대해 <math>p\mid a_i</math>이다. 따라서 <math>p</math>는 <math>a_i</math>와 <math>m</math>을 모두 나누고, 이는 <math>m</math>과 <math>a_i</math>가 서로소라는 가정에 모순이다. === 도움정리 2 === 양의 정수 <math>m</math>과 <math>a_1,a_2,\cdots,a_n</math>에 대해, <math>m</math>이 <math>a_1,a_2,\cdots,a_n</math>의 각각의 배수이면, <math>m</math>은 <math>a_1,a_2,\cdots,a_n</math>의 [[최소공배수]]의 배수이다. 증명 :<math>a_1,a_2,\cdots,a_n</math>의 최소공배수를 <math>L</math>이라 하자. 그럼 [[나눗셈 정리]]에 의해, <math>m=qL+r</math>을 만족하는 정수 <math>q,r</math>이 유일하게 존재한다 (단, <math>0\leq r< L</math>). 그런데 <math>a_i</math>는 <math>m</math>과 <math>L</math>을 모두 나누므로, <math>r</math>도 나눠야 한다. 이는 모든 <math>i</math>에 대해 성립하므로, <math>r</math>은 <math>L</math>보다 작은 모든 <math>a_i</math>의 공배수이고, 이는 <math>r=0</math>일 때만 가능하다. 따라서 <math>m=qL</math>이고, <math>m</math>은 <math>L</math>의 배수이다. === 도움정리 3 === 양의 정수 <math>a_1,a_2,\cdots,a_n</math>에 대해, <math>a_1,a_2,\cdots,a_n</math>이 쌍마다 서로소이면, <math>\text{lcm}\left(a_1,a_2,\cdots,a_n\right)=a_1a_2\cdots a_n</math>이다. 증명은 자명하므로 생략한다. === 존재성 === <math>m=m_1m_2\cdots m_n,\,n_k=m/m_k</math>라 정의하자. 도움정리 1로 부터 <math>\gcd\left(n_k,m_k\right)=1</math>이다. 따라서, <math>s_kn_k+t_km_k=1</math>을 만족하는 정수 <math>s_k,t_k</math>가 존재한다.<ref>[[최대공약수]] 참조.</ref> 이는 곧, <math>s_kn_k\equiv1\pmod{m_k}</math>이다. 이제 <math>x=a_1n_1s_1+a_2n_2s_2+\cdots+a_nn_ns_n</math>이라 하자. 만약 <math>j\neq k</math>면 <math>m_k\mid n_j</math>이므로, <math>x\equiv a_kn_ks_k\equiv a_k\cdot1\equiv a_k\pmod{m_k}</math>이다. 이는 임의의 <math>k</math>에 대해 성립하므로, <math>x</math>는 주어진 연립합동식의 한 해임을 알 수 있다. === 유일성 === <math>x,y</math>가 주어진 연립합동식의 해라고 가정하자. 그러면 임의의 <math>k</math>에 대해 <math>x\equiv a_k\equiv y\pmod{m_k}</math>이고, 따라서 <math>x-y\equiv0\pmod{m_k}</math>이다. 즉, <math>x-y</math>는 모든 <math>m_k</math>의 배수이고, 도움정리 2에 의해 <math>\text{lcm}\left(m_1,m_2,\cdots,m_n\right)\mid\left(x-y\right)</math>이다. 그런데 <math>m_1,m_2,\cdots,m_n</math>이 쌍마다 서로소이므로, 도움정리 3에 의해 <math>\text{lcm}\left(m_1,m_2,\cdots,m_n\right)=m_1m_2\cdots m_n=m\mid\left(x-y\right)</math>. 따라서 <math>x\equiv y\pmod m</math>. 이는 곧 주어진 연립합동식의 해가 유일함을 의미한다. === 예시 === 맨 위의 문제를 풀어보도록 하자. 방법은 해의 존재성을 증명하는 것과 비슷하다. :3, 5, 7이 쌍마다 서로소이므로 주어진 연립 합동식은 <math>3\times5\times7=105</math>에 대하여 유일한 해를 가진다. <math>m=105,n_1=35,n_2=21,n_3=15</math>라 하자.<br/><math>\begin{align*}n_1s_1\equiv35s_1\equiv2s_1\equiv1\pmod3\\n_2s_2\equiv21s_2\equiv s_2\equiv1\pmod5\\n_3s_3\equiv15s_3\equiv s_3\equiv1\pmod7\end{align*}</math><br/>을 풀면 <math>s_1=2,s_2=1,s_3=1</math>가 해임을 알 수 있다.<ref>여러 값중 아무거나 고르면 된다.</ref> 그러므로 <math>x\equiv a_1n_1s_1+a_2n_2s_2+a_3n_3s_3\equiv2\cdot35\cdot 2+3\cdot21\cdot1+2\cdot15\cdot1\equiv233 \equiv23\pmod{105}</math>이다.<p/>따라서 <math>x\equiv23\pmod{105}</math>가 주어진 연립 합동식의 해이다. == 추상대수학에서 == [[추상대수학]]버전의 정리도 존재한다. {{^|<math>k\left[x\right]</math> 버전}} #\(k\)가 [[체 (수학)|체]]이고, <math>f\left(x\right),\,f'\left(x\right)\in k\left[x\right]</math>가 [[서로소]]라면, <math>k\left[x\right]</math>의 두 원소 <math>b\left(x\right),\,b'\left(x\right)</math>에 대해, <math>c-b\in\left(f\right)</math>이고 <math>c-b'\in\left(f\right)</math>인 <math>c\left(x\right)\in k\left[x\right]</math>가 존재한다. 더욱이, <math>d\left(x\right)</math>가 또 다른 해라면, <math>c-d\in\left(ff'\right)</math>. #\(k\)가 [[체 (수학)|체]]이고, <math>f\left(x\right),\,g\left(x\right)\in k\left[x\right]</math>가 [[서로소]]라면, <math>k\left[x\right]/\left(f\left(x\right)g\left(x\right)\right)\cong k\left[x\right]\left(f\left(x\right)\right)\times k\left[x\right]/\left(g\left(x\right)\right)</math>. {{^|일반화된 버전}} \(R\)이 [[환 (수학)|가환환]]이고, <math>I_1,\,I_2,\,\ldots,\,I_n</math>이 쌍끼리 [[서로소]]인 [[아이디얼]]이라고 하자. 만약 <math>a_1,\,a_2,\,\ldots,\,a_n\in R</math>이면, <math>r+I_i=a_i+I_i,\,\forall i</math>를 만족하는 <math>r\in R</math>이 존재한다. == 같이 보기 == *[[나누어떨어짐]] *[[모듈러산술]] *[[환 (수학)|환]] {{각주}} [[분류:정수론]][[분류:추상대수학]] [[분류:수학 정리]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:Skin (원본 보기) (준보호됨)틀:^ (편집) 틀:각주 (원본 보기) (준보호됨)틀:인용문 (원본 보기) (준보호됨)