중국인의 나머지 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

중국인의 나머지 정리는 여러 개의 연립 합동식 해의 존재성과 유일성에 대한 정리이다. 이 정리는 5세기 중국 수학서 《손자산경》에 처음 등장했으며, 이후 진구소의 《수서구장》에서 일반화되었다. 중국인의 나머지 정리는 정수론, 대수학, 암호학 등 다양한 분야에 응용되며, 특히 괴델 수의 구성, 고속 푸리에 변환, RSA 암호화 등에 활용된다. 이 정리는 서로소인 정수 n₁, ..., nₖ와 임의의 정수 a₁, ..., aₖ에 대해 연립 합동식 x ≡ a₁ (mod n₁) ... x ≡ aₖ (mod nₖ)의 해가 존재하며, 두 해는 N (nᵢ의 곱)을 법으로 합동이라는 것을 보장한다. 해는 체계적인 탐색, 체로 거르기, 구성적 증명 또는 직접 구성을 통해 계산할 수 있으며, 선형 디오판토스 방정식 시스템으로도 표현 가능하다. 중국인의 나머지 정리는 서로소가 아닌 법으로도 일반화될 수 있으며, 환의 서로소 아이디얼을 사용하여 확장될 수 있다.

더 읽어볼만한 페이지

중국 수학 - 산가지
산가지는 중국에서 기원한 2천 년 이상 된 계산 도구이자 막대 배열로 숫자를 나타내는 기수법으로, 사칙연산, 제곱근, 고차 방정식 해법 등에 활용되었으나 주판 발달로 쇠퇴, 일본에서 대수 기호로 발전, 현대에는 유니코드에 등록되어 재조명되고 있다.
중국 수학 - 구장산술
구장산술은 중국의 고대 수학을 집대성한 아홉 개의 장으로 구성된 책으로, 다양한 수학 문제와 해법을 제시하며 동양 수학 발전에 큰 영향을 미쳤다.
모듈러 산술 - 이산 로그
이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
모듈러 산술 - 페르마의 소정리
페르마의 소정리는 소수 p와 정수 a에 대해 a^p와 a가 법 p에 대해 합동이라는 정리로, p가 a의 배수가 아닐 경우 a^(p-1) ≡ 1 (mod p)로 표현되며, 소수 판별법과 RSA 암호 시스템 등에 응용된다.
수론 정리 - 페르마의 마지막 정리
페르마의 마지막 정리는 3 이상의 정수 n에 대해 xⁿ + yⁿ = zⁿ을 만족하는 양의 정수 x, y, z는 존재하지 않는다는 정리이며, 앤드루 와일스가 모듈러성 정리를 이용하여 1995년에 증명했다.
수론 정리 - 라그랑주 네 제곱수 정리
라그랑주 네 제곱수 정리는 모든 양의 정수를 네 개의 정수 제곱수의 합으로 나타낼 수 있다는 정리이다.

중국인의 나머지 정리
기본 정보
명칭
한국어 명칭	중국인의 나머지 정리
한자 표기	中國人의剩餘定理
로마자 표기	Junggugin-ui neomeoji jeongni
영어 명칭	Chinese remainder theorem
중국어 명칭	中国剩余定理
병음	Zhōngguó shèngyú dìnglǐ
일본어 명칭	中国の剰余定理
가나 표기	ちゅうごくのじょうよていり
로마자 표기	Chūgoku no jōyo teiri
내용
설명	서로 소인 자연수에 대한 연립 합동식 해의 존재성과 유일성을 보장하는 정수론의 정리

2. 역사

중국인의 나머지 정리는 5세기경 중국의 수학책 《손자산경》에 처음 등장하는 것으로 알려져 있다.^[1] 《손자산경》 하권(下卷) 문제 26번에는 다음과 같은 문제가 나온다.

이는 3, 5, 7로 나눈 나머지가 각각 2, 3, 2인 수를 찾는 문제였다. 이 문제는 다음과 같은 연립 합동 방정식으로 표현될 수 있다.

: $x\equiv2\pmod3\equiv3\pmod5\equiv2\pmod7$

《손자산경》의 풀이는 각 합동식에서 나머지를 하나하나씩 맞추어 가는 알고리즘이다.

이후 남송 시대의 수학자 진구소(秦九韶)는 1247년에 저술한 《수서구장》(數書九章)에서 이 문제의 해법을 더 일반화했다.^[6] 진구소는 ''대연술''(大衍術)이라는 완전한 해법을 제시했다. 그는 송나라의 부패와 무능에 맞서 싸운 인물로 평가받기도 한다. 19세기 초, 영국 선교사 알렉산더 와일리는 진구소의 업적을 서구에 소개했다.^[7]

카를 프리드리히 가우스는 1801년 저서 《산술 연구》에서 합동식의 개념을 도입하고 중국인의 나머지 정리를 체계적으로 정리했다.^[9] 가우스는 달력과 관련된 문제, 즉 "태양 주기, 음력 주기 및 로마 인딕션과 관련하여 특정 주기 번호를 갖는 연도를 찾는 것"에 대해 중국인의 나머지 정리를 설명했다.^[10]

2. 1. 한국에서의 수용과 발전

손자산경은 일찍이 한국에 전래되어 조선 시대 산학(算學)에 큰 영향을 미쳤다. 조선 후기 실학자 최석정은 구수략에서 중국인의 나머지 정리를 "구일술(求一術)"이라는 이름으로 소개하고, 다양한 문제에 응용했다. 최석정은 노론 명문가 출신이지만, 소론 및 남인 학자들과 교류하며 당파에 얽매이지 않는 학문적 태도를 보였다. 현대 한국 수학계는 중국인의 나머지 정리를 정수론, 대수학, 암호학 등 다양한 분야에서 연구하고 있다.

3. 정의

서로소인 1보다 큰 정수 ''n''₁, ..., ''n''_''k''와 임의의 정수 ''a''₁, ..., ''a''_''k''가 주어졌을 때, 다음 연립 합동식

: $\begin{align}x &\equiv a_1 \pmod{n_1} \\&\,\,\,\vdots \\x &\equiv a_k \pmod{n_k},\end{align}$

은 해를 가지며, 이 해는 ''N'' = ''n''₁''n''₂...''n''_''k''을 법으로 하였을 때 유일하다.^[12]

이는 ''n''_''i'' 들이 서로소이고, 0 ≤ ''a''_''i'' < ''n''_''i'' 인 정수 ''a''₁, ..., ''a''_''k'' 가 주어지면, 0 ≤ ''x'' < ''N'' 이고 ''x''를 ''n''_''i'' 로 나눈 나머지가 모든 ''i''에 대해 ''a''_''i'' 인 정수 ''x''가 유일하게 존재한다는 것을 의미한다.

가장 기본적인 형태는 다음과 같다.

> 서로소인 두 정수 ''m'', ''n''과 임의의 정수 ''a'', ''b''가 주어졌을 때, 다음 연립 합동식

> ''x'' ≡ ''a'' (mod ''m''),

> ''x'' ≡ ''b'' (mod ''n'')

> 을 만족하는 정수 ''x''가 ''mn''을 법으로 하여 유일하게 존재한다.^[24]
해의 존재 증명: 서로소인 두 정수 ''m'', ''n''에 대해, 유클리드 호제법에 의해 ''mu'' + ''nv'' = 1을 만족하는 정수 ''u'', ''v''가 존재한다. 이때,

: ''mu'' ≡ 1 (mod ''n''),

: ''nv'' ≡ 1 (mod ''m'')

이 성립하므로, ''x'' = ''anv'' + ''bmu'' 라고 하면,

: ''x'' ''= a''(1 − ''mu'') ''+ bmu = a +'' (''b − a'') ''mu ≡ a'' (mod ''m'')

이고,

: ''x'' = ''anv'' + ''b''(1 − ''nv'') ''= b'' + (''a'' − ''b'') ''nv ≡ b'' (mod ''n'')

이므로 ''x''는 주어진 연립 합동식의 해가 된다.
해의 유일성 증명: ''y''를 임의의 해라고 하면, ''x'' − ''y''는

: ''x'' − ''y'' ≡ 0 (mod ''m''),

: ''x'' − ''y'' ≡ 0 (mod ''n'')

을 만족한다. 따라서 ''x'' − ''y''는 ''m''과 ''n''의 공배수이지만, ''m''과 ''n''은 서로소이므로, ''x'' − ''y''는 그들의 최소공배수 ''mn''의 배수가 되어,

: ''x'' − ''y'' ≡ 0 (mod ''mn'')

즉, ''x''와 ''y''는 법 ''mn''에 관해 합동이다.

3. 1. 일반적인 경우 (가환환)

어떤 환

R

속의 두 아이디얼

\mathfrak a,\mathfrak b\subset R

가

\mathfrak a+\mathfrak b=R

를 만족시키면, 이 두 아이디얼을 '''서로소'''(coprime^영어)라고 한다.

R

가 (곱셈 단위원을 갖는) 가환환이고,

\mathfrak n_1,\dots,\mathfrak n_k\subset R

가 서로소 아이디얼들이라고 하자. 또한, 이 아이디얼들의 곱을

:

\mathfrak n=\prod_{i=1}^k\mathfrak n_i

라고 놓자. 그렇다면 다음이 성립한다.

:

\mathfrak n=\bigcap_{i=1}^k\mathfrak n_i

:

R/\mathfrak n\cong\prod_{i=1}^k R/\mathfrak n_i

여기서, 환 동형사상은 구체적으로 다음과 같다.

:

r+\mathfrak n\mapsto(r+\mathfrak n_1,\dots,r+\mathfrak n_k)

추상대수학에서, 만약 ''n''_''i''가 상호 소수이면, 다음의 사상

:

x \bmod N \;\mapsto\;(x \bmod n_1,\, \ldots,\, x \bmod n_k)

는 환 동형사상을 정의한다.^[13]

:

\mathbb{Z}/N\mathbb{Z} \cong \mathbb{Z}/n_1\mathbb{Z} \times \cdots \times \mathbb{Z}/n_k\mathbb{Z}

이는 ''N''을 법으로 한 정수의 환과 ''n''_''i''를 법으로 한 정수들의 환들의 직접 곱 사이의 동형사상이다.

환

R

의 양쪽 아이디얼을

I_1, I_2, \dots, I_k

라고 하고,

I

를 그들의 교집합이라고 하자. 아이디얼이 쌍별로 서로소이면, 다음의 동형이 성립한다.

:

\begin{align}R/I &\to (R/I_1) \times \cdots \times (R/I_k) \\x \bmod I &\mapsto (x \bmod I_1,\, \ldots,\, x \bmod I_k),\end{align}

여기서 "

x \bmod I

"는 아이디얼

I

에 의해 정의된 몫환에서 원소

x

의 상을 나타낸다.

또한,

R

이 가환이면, 쌍별로 서로소인 아이디얼의 아이디얼 교집합은 그들의 곱과 같다. 즉,

:

I= I_1\cap I_2 \cap\cdots\cap I_k= I_1I_2\cdots I_k,

만약 모든

i \ne j

에 대해

I_i

와

I_j

가 서로소이면.

''R''을 단위원을 갖는 환으로 하고, ''R''의 양쪽 아이디얼 ''I''₁, ''I''₂, ..., ''I_k''가 어느 두 개도 서로소라고 가정한다(즉, ''i'' ≠ ''j''이면 ''I_i'' + ''I_j'' = ''R''이 성립한다). 이 때, 임의로 주어진 ''a''₁, ''a''₂, ..., ''a_k'' ∈ ''R''에 대하여,

\begin{align}x &\equiv a_1 \pmod{I_1}, \\x &\equiv a_2 \pmod{I_2}, \\& \vdots \\x &\equiv a_k \pmod{I_k}\end{align}

를 만족하는 ''x'' ∈ ''R''이 아이디얼

\textstyle I = \bigcap_{i=1}^k I_i

를 법으로 하여 유일하게 존재한다. 다시 말해, 자연스러운 환 준동형

R \to \prod_{i=1}^k R/I_i, \; x \mapsto (x + I_1, x + I_2, \dotsc , x + I_k)

는 전사이며, 준동형 정리에 의해 환 동형

R/I \cong \prod_{i=1}^k R/I_i

를 얻을 수 있다. 이것도 중국인의 나머지 정리라고 불린다. 또한 ''R''이 가환환일 때,

I_1 I_2 \dotsm I_k \supset \bigcap_{i=1}^k I_i

가 두 개의 서로 다른 아이디얼이 서로소이기 때문에 따르며, 역방향의 포함 관계는 일반적으로 성립하므로,

I_1 I_2 \dotsm I_k = \bigcap_{i=1}^k I_i

가 성립한다.

3. 2. 정수환에 대한 경우

서로소인 음이 아닌 정수

n_1, n_2, \cdots, n_k

가 주어졌을 때,

n=\prod_{i=1}^kn_i

라고 하자. 그러면 임의의 정수

k

-튜플

(a_1,a_2,\dots,a_k)\in\prod_{i=1}^k\mathbb Z/n_i

에 대해, 다음 연립 합동 방정식의 해

a\in\mathbb Z/n

은 항상 유일하게 존재한다.

:

a\equiv a_i\pmod{n_i}\quad\forall i=1,\dots, k

이에 따라 다음과 같은 환 동형사상이 존재한다.

:

\mathbb Z/n\cong\prod_{i=1}^k\mathbb Z/n_i

4. 증명

中國餘數定理|중국인의 나머지 정리^중국어의 증명은 주로 해의 존재성과 유일성을 나누어 증명한다.

해의 존재성은 구성적 증명(constructive proof) 또는 직접 구성(direct construction)을 통해 보일 수 있다. 환이 정수환 $\mathbb Z$ 인 경우, 각 $n_i$ 에 대해 $n/n_i$ 와 $n_i$ 는 서로소이므로, $r_i n_i + s_i (n/n_i) = 1$ 인 정수 $r_i, s_i$ 가 존재한다. 여기서 $e_i = s_i (n/n_i)$ 라고 놓으면,

: $e_i \equiv 1 \pmod {n_i}$

: $e_i \equiv 0 \pmod {n_j}$ ( $i \ne j$ )

가 성립한다. 여기에서 $a = \sum_i a_i e_i$ 로 놓으면, 임의의 $i$ 에 대해 $a \equiv a_i \pmod {n_i}$ 가 성립한다. 즉, $a$ 가 바로 구하는 해 중 하나이다.

베주 항등식에 따르면, $n_1$ 과 $n_2$ 가 서로소일 때, $m_1n_1+m_2n_2=1$ 를 만족하는 정수 $m_1$ 과 $m_2$ 가 존재한다. 이 $m_1$ 과 $m_2$ 는 확장 유클리드 알고리즘을 통해 계산할 수 있다. 그러면 해는 $x = a_1m_2n_2+a_2m_1n_1$ 와 같이 주어진다.

해의 유일성은 귀류법을 사용하여, 두 해의 차이가 모든 $n_i$ 의 배수임을 보이는 방식으로 증명한다. $\mathbb Z/n$ 속에서의 유일성을 증명하기 위해, 두 해 $x, y$ 가 존재한다고 가정하면, $x \equiv a_i, y \equiv a_i \pmod {n_i}$ 이므로 $x-y$ 는 모든 $n_i$ 의 배수이고, 따라서 $x-y$ 는 $n_1 n_2 \cdots n_k = n$ 의 배수이다. 즉, $x \equiv y \pmod n$ 이므로, $\mathbb Z/n$ 속에서는 항상 유일한 해가 존재한다.

5. 계산

중국인의 나머지 정리의 해를 계산하는 방법은 여러 가지가 있다.

체계적인 탐색: 0부터 N까지의 정수를 차례로 대입하여 해를 찾는 방법이다.
체로 거르기: 해가 속하는 등차수열을 이용하여 해를 빠르게 찾는 방법이다.
구성적 증명 활용: 베주 항등식과 확장 유클리드 알고리즘을 이용하여 해를 구하는 방법이다.
직접 구성: 부분 분수 분해를 이용하여 해를 구하는 방법이다. 라그랑주 보간법과 에르미트 보간법은 이 방법의 특수한 경우이다.
선형 디오판토스 방정식 시스템: 주어진 합동식 체계를 선형 디오판토스 방정식 시스템으로 변환하여 해를 구하는 방법이다.

손자산경에 나오는 문제, 즉 다음 연립 합동식을 만족하는 정수 ''x''를 구하는 예를 통해 계산 방법을 설명할 수 있다.

''x'' ≡ 2 (mod 3),

''x'' ≡ 3 (mod 5),

''x'' ≡ 2 (mod 7)

점진적인 대입(구성적 증명 활용의 특수한 경우):

1. 첫 번째 식에서 ''x'' = 3''m''₁ + 2 (''m''₁은 정수)로 나타낸다.

2. 이를 두 번째 식에 대입하면 3''m''₁ ≡ 1 (mod 5)를 얻는다.

3. 양변에 2를 곱하면 ''m''₁ ≡ 2 (mod 5)를 얻는다. ('''Z'''/5'''Z'''에서 2가 3의 곱셈에 대한 역원이기 때문)

4. ''m''₁ = 5''m''₂ + 2 (''m''₂는 정수)로 나타내고, ''x'' = 15''m''₂ + 8을 얻는다.

5. 이를 세 번째 식에 대입하면 15''m''₂ + 8 ≡ 2 (mod 7)을 얻는다.

6. ''m''₂ ≡ -6 ≡ 1 (mod 7)이므로, ''m''₂ = 7''m₃'' + 1 (''m₃''은 정수)로 나타낸다.

7. 최종적으로 ''x'' = 105''m₃'' + 23, 즉 ''x'' ≡ 23 (mod 105)를 얻는다.

확장 유클리드 호제법 활용(구성적 증명 활용):

1. 3과 35, 5와 21, 7과 15는 각각 서로소이므로, 확장 유클리드 호제법을 이용하여 다음 부정 방정식의 정수해를 구한다.

3 × 12 + 35 × (-1) = 1,

5 × (-4) + 21 × 1 = 1,

7 × (-2) + 15 × 1 = 1

2. 이를 통해 다음 합동식이 성립함을 알 수 있다.

-35 ≡ 1 (mod 3),

21 ≡ 1 (mod 5),

15 ≡ 1 (mod 7).

3. 연립 합동식 ''x'' ≡ ''a''₁ (mod 3), ''x'' ≡ ''a''₂ (mod 5), ''x'' ≡ ''a''₃ (mod 7)의 해는 ''x'' = -35''a''₁ + 21''a''₂ + 15''a''₃이다.

4. 해는 105를 법으로 유일하며, 모든 해는 ''k''를 임의의 정수로 하여 -35''a''₁ + 21''a''₂ + 15''a''₃ + 105''k''로 표현된다.

5. 1. 체계적인 탐색(Systematic search)

0부터 N까지의 정수를 차례로 확인하여 해를 찾는 방법이다. 해를 찾기 위해 0부터 N까지의 정수를 차례로 확인하면 된다.

이 방법은 매우 간단하지만, 매우 비효율적이다. 예를 들어, 해인 39를 찾기 위해 0을 포함하여 40개의 정수를 확인해야 한다. 이는 입력 크기가 상수 인수를 제외하고 N의 자릿수이고 평균 연산 횟수가 N의 순서이므로 지수 시간 알고리즘이다.

따라서 이 방법은 손으로 계산하거나 컴퓨터에서 거의 사용되지 않는다.

5. 2. 체로 거르기(Search by sieving)

해의 탐색은 체로 거름으로써 극적으로 더 빠르게 할 수 있다. 이 방법의 경우, 일반성을 잃지 않고,

0\le a_i 라고 가정한다 (그렇지 않은 경우, 각 a_i 를 n_i 로 나눈 나머지로 대체하는 것으로 충분하다). 이는 해가 다음 등차수열 에 속한다는 것을 의미한다.

:

a_1, a_1 + n_1, a_1+2n_1, \ldots

이 값들을

n_2

로 모듈로 계산하여 검사하면 결국 처음 두 합동식의 해

x_2

를 찾을 수 있다. 그러면 해는 다음 등차수열에 속한다.

:

x_2, x_2 + n_1n_2, x_2+2n_1n_2, \ldots

이 값들을

n_3

로 모듈로 계산하여 검사하고, 모든 모듈로를 검사할 때까지 계속하면 결국 해가 나온다.

이 방법은 모듈로가 감소하는 값으로 정렬된 경우, 즉

n_1>n_2> \cdots > n_k

인 경우 더 빠르다. 예시의 경우, 다음 계산이 이루어진다. 먼저 5를 모듈로 한 4에 합동인 숫자, 즉 4, 9, 14, ...를 고려한다. 이 각각에 대해, 4를 모듈로 한 나머지를 계산하여 4를 모듈로 한 3에 합동인 숫자를 얻을 때까지 계산한다. 그런 다음 각 단계마다 20 (5 × 4)을 더하고, 3을 모듈로 한 나머지 만을 계산하여 진행할 수 있다. 이는 다음과 같다.

4 mod 4 → 0. 계속
4 + 5 = 9 mod 4 → 1. 계속
9 + 5 = 14 mod 4 → 2. 계속
14 + 5 = 19 mod 4 → 3. OK, 3을 모듈로 한 나머지를 고려하고 매번 5 × 4 = 20을 더하여 계속한다.
19 mod 3 → 1. 계속
19 + 20 = 39 mod 3 → 0. OK, 이것이 결과이다.

이 방법은 모듈로의 곱이 너무 크지 않은 손으로 계산할 때 잘 작동한다. 그러나 모듈로의 곱이 매우 큰 경우에는 다른 방법보다 훨씬 느리다. 체계적인 탐색보다 극적으로 빠르지만, 이 방법은 또한 지수 시간 복잡성을 가지므로 컴퓨터에서는 사용되지 않는다.^[15]

5. 3. 구성적 증명 활용

베주 항등식에 따르면, 정수

m_1

과

m_2

가 존재하여

m_1n_1+m_2n_2=1

이 성립한다. 이 정수들은 확장 유클리드 알고리즘을 통해 계산할 수 있다.^[15] 이때, 연립 합동식의 해는

x = a_1m_2n_2+a_2m_1n_1

이다.

이러한 구성을 통해 x의 존재성을 확인할 수 있다. 구성은 두 단계로 나뉜다. 먼저 두 개의 법(modulus)에 대한 문제를 해결하고, 그 해를 수학적 귀납법을 사용하여 일반적인 경우로 확장한다.

두 모듈의 경우에서 해는 모듈의 베주 계수 계산, 곱셈, 덧셈, 그리고 모듈로

n_1n_2

감소(결과를 구간

(0, n_1n_2-1)

내에서 얻기 위해)를 통해 얻을 수 있다.

두 개 이상의 모듈의 경우, 두 모듈에 대한 방법을 반복하여 두 개의 합동식을 모듈의 곱에 대한 단일 합동식으로 대체할 수 있다. 이 과정을 반복하면 모든 모듈 곱의 자릿수에 대해 2차 복잡도를 가진 해를 얻는다.

모듈을 곱이 유사한 크기를 갖는 쌍으로 분할하고, 각 쌍에 두 모듈 방법을 병렬로 적용한 다음, 모듈 수를 대략 2로 나누어 반복하는 방법도 있다. 이 방법은 알고리즘의 쉬운 병렬화를 가능하게 한다.

5. 4. 직접 구성

孫子定理|쑨쯔 딩리^중국어에서 주어진 나머지 정리에 관한 명제는 주 아이디얼 정역으로 일반화될 수 없지만, 유클리드 정역으로는 쉽게 일반화할 수 있다. 체 위의 일변수 다항식은 정수가 아닌 유클리드 정역의 대표적인 예이다. 따라서 체

K

에 대한 링

R=K[X]

의 경우에 대해 정리를 서술할 수 있다. 일반적인 유클리드 정역에 대한 정리를 얻으려면, 차수를 유클리드 정역의 유클리드 함수로 대체하면 된다.

다항식에 대한 중국인의 나머지 정리는 다음과 같다.

P_i(X)

(법)가

i = 1, \dots, k

에 대해

R=K[X]

에서 서로소 다항식이라고 하자.

d_i =\deg P_i

를

P_i(X)

의 차수라고 하고,

D

를

d_i

의 합이라고 하자.

만약

A_i(X), \ldots,A_k(X)

가 모든

i

에 대해

A_i(X)=0

또는

\deg A_i 인 다항식이라면, \deg P 이고 P_i(X) 에 의한 P(X) 의 유클리드 나눗셈의 나머지가 모든 i 에 대해 A_i(X) 인 다항식 P(X) 가 유일하게 존재한다.

해는 구성적 증명 또는 직접 증명과 같이 구성할 수 있다. 그러나 후자의 구성은 확장된 유클리드 알고리즘 대신 부분 분수 분해를 사용하여 다음과 같이 단순화할 수 있다.

다음과 같은 합동식을 만족하는 다항식

P(X)

를 찾는다고 하자.

:

P(X)\equiv A_i(X) \pmod {P_i(X)},

(

i=1,\ldots,k

에 대해)

다음과 같은 다항식을 고려한다.

:

\begin{align}Q(X) &= \prod_{i=1}^{k}P_i(X) \\Q_i(X) &= \frac{Q(X)}{P_i(X)}.\end{align}

1/Q(X)

의 부분 분수 분해는 차수가

\deg S_i(X) < d_i,

인

k

개의 다항식

S_i(X)

를 제공하며, 다음을 만족한다.

:

\frac{1}{Q(X)} = \sum_{i=1}^k \frac{S_i(X)}{P_i(X)},

따라서

:

1 = \sum_{i=1}^{k}S_i(X) Q_i(X).

그러면 합동 연립 방정식의 해는 다음과 같은 다항식으로 주어진다.

:

\sum_{i=1}^k A_i(X) S_i(X) Q_i(X).

실제로 다음이 성립한다.

:

\sum_{i=1}^k A_i(X) S_i(X) Q_i(X)= A_i(X)+ \sum_{j=1}^{k}(A_j(X) - A_i(X)) S_j(X) Q_j(X) \equiv A_i(X)\pmod{P_i(X)},

(

1 \leq i \leq k.

에 대해)

이 해는

D=\sum_{i=1}^k d_i.

보다 큰 차수를 가질 수 있다. 차수가

D

보다 작은 유일한 해는

P_i(X)

에 의한

A_i(X)S_i(X)

의 유클리드 나눗셈의 나머지

B_i(X)

를 고려하여 얻을 수 있다. 이 해는 다음과 같다.

:

P(X)=\sum_{i=1}^k B_i(X) Q_i(X).

다항식에 대한 중국인의 나머지 정리의 특수한 경우는 라그랑주 보간법이다. 이를 위해 차수 1인

k

개의 모닉 다항식을 고려한다.

:

P_i(X)=X-x_i.

만약

x_i

가 모두 다르다면, 이들은 쌍별로 서로 소이다. 다항식 나머지 정리에 의해, 다항식

P(X)

를

P_i(X)

로 나눈 나머지는

P(x_i)

이다.

이제

A_1, \ldots, A_k

를

K

에 있는 상수(차수 0의 다항식)라고 하자. 라그랑주 보간법과 중국인의 나머지 정리는 모두 다음을 만족하는 차수가

k

보다 작은 유일한 다항식

P(X)

의 존재를 주장한다.

:

P(x_i)=A_i,

(모든

i

에 대해)

라그랑주 보간법 공식은 이 경우 위에서 제시된 해 구성의 결과이다. 더 정확하게는,

:

\begin{align}Q(X)  &= \prod_{i=1}^{k}(X-x_i) \\[6pt]Q_i(X) &= \frac{Q(X)}{X-x_i}.\end{align}

\frac{1}{Q(X)}

의 부분 분수 분해는 다음과 같다.

:

\frac{1}{Q(X)} = \sum_{i=1}^k \frac{1}{Q_i(x_i)(X-x_i)}.

실제로 우변을 통분하면 다음을 얻는다.

:

\sum_{i=1}^k \frac{1}{Q_i(x_i)(X-x_i)}= \frac{1}{Q(X)} \sum_{i=1}^k \frac{Q_i(X)}{Q_i(x_i)},

여기서 분자는 1과 같다. 왜냐하면

k

보다 작은 차수의 다항식이면서

X

의

k

개의 서로 다른 값에 대해 값 1을 취하기 때문이다.

위의 일반적인 공식을 사용하면 라그랑주 보간법 공식을 얻는다.

:

P(X)=\sum_{i=1}^k A_i\frac{Q_i(X)}{Q_i(x_i)}.

에르미트 보간법은 다항식에 대한 중국인의 나머지 정리의 응용이며, 임의 차수의 법을 포함할 수 있다(라그랑주 보간법은 1차 법만 포함한다).

이 문제는 가능한 가장 낮은 차수의 다항식을 찾는 것으로, 이 다항식과 그 첫 번째 도함수가 몇몇 고정된 점에서 주어진 값을 갖도록 하는 것이다.

더 정확하게 설명하면,

x_1, \ldots, x_k

를 체

K

의

k

개 원소라고 하고,

i=1,\ldots, k

에 대해

a_{i,0}, a_{i,1}, \ldots, a_{i,r_i-1}

를

x_i

에서 구하는 다항식의 처음

r_i

개 도함수 값이라고 하자(0차 도함수, 즉 다항식 자체의 값 포함). 문제는

P(X)

의 ''j''번째 도함수가

i=1,\ldots,k

및

j=0,\ldots,r_j

에 대해

x_i

에서 값

a_{i,j}

을 갖는 다항식

P(X)

를 찾는 것이다.

다음 다항식을 고려해 보자.

:

P_i(X) = \sum_{j=0}^{r_i - 1}\frac{a_{i,j}}{j!}(X - x_i)^j.

이것은

x_i

에서 미지 다항식

P(X)

의

r_i-1

차 테일러 다항식이다. 따라서 다음이 성립해야 한다.

:

P(X)\equiv P_i(X) \pmod {(X-x_i)^{r_i}}.

역으로, 이러한

k

개 합동식을 만족하는 모든 다항식

P(X)

는, 특히 모든

i=1, \ldots, k

에 대해 다음을 만족한다.

:

P(X)= P_i(X) +o(X-x_i)^{r_i-1}

따라서

P_i(X)

는

x_i

에서

r_i - 1

차 테일러 다항식이며, 즉

P(X)

는 초기 에르미트 보간법 문제를 해결한다.

중국인의 나머지 정리는 이러한

k

개 합동식을 만족하는

r_i

의 합보다 낮은 차수의 다항식이 정확히 하나 존재한다고 주장한다.

해

P(X)

를 계산하는 방법에는 여러 가지가 있다. 해당 부분의 시작 부분에 설명된 방법을 사용할 수 있다. 또한 구성적 증명 또는 직접 증명에 제공된 구성을 사용할 수도 있다.

정리에 의해 해가 존재한다는 것은 보장되지만, 실제로 해를 계산할 수 있는지는 별개의 문제이다. 그러나 중국인의 나머지 정리의 경우에는 해를 계산하는 것도 용이하며, 그 방법도 몇 가지 있다.

『손자산경』의 문제를 생각해 보자. 즉, 다음 연립 합동식을 동시에 만족하는 정수 ''x''를 구하는 문제이다.

''x'' ≡ 2 (mod 3),

''x'' ≡ 3 (mod 5),

''x'' ≡ 2 (mod 7)

먼저 첫 번째 식에서 ''x'' = 3''m''₁ + 2 (''m''₁ ∈ '''Z''')로 나타낼 수 있다. 이것을 두 번째 식에 대입하고 양변에서 2를 빼면,

3''m''₁ ≡ 1 (mod 5).

을 얻는다. 이 식의 양변에 2를 곱하면, (좌변) = 6''m''₁ = 5''m''₁ + ''m''₁ ≡ ''m''₁ (mod 5)이다(이것은 '''Z'''/5'''Z'''에서 2가 3의 곱셈에 대한 역원이라는 것에 지나지 않는다). 따라서,

''m''₁ ≡ 2 (mod 5)

을 얻는다. 따라서 ''m''₁ = 5''m''₂ + 2 (''m''₂ ∈ '''Z''')로 나타낼 수 있으며, 이를 통해 ''x'' = 15''m''₂ + 8을 얻는다. 더 나아가 이것을 연립 합동식의 세 번째 식에 대입하면,

15''m''₂ + 8 ≡ 2 (mod 7)

을 얻는다. 이 식의 양변에서 8을 빼고, 15''m''₂ = 14''m''₂ + ''m''₂ ≡ ''m''₂ (mod 7)임을 주의하면,

''m''₂ ≡ −6 (mod 7).

더욱이 이것은 −6 ≡ 1 (mod 7)이므로

''m''₂ ≡ 1 (mod 7)

로 다시 쓸 수 있으므로, ''m''₂ = 7''m₃'' + 1 (''m₃'' ∈ '''Z''')로 나타낼 수 있으며, 이를 통해 ''x'' = 105''m₃'' + 23을 얻는다. 즉,

''x'' ≡ 23 (mod 105)

가 구하는 해이다. 이 방법은 계산이 번거로워진다는 단점이 있지만, 연립 합동식의 법이 서로 소가 되지 않는 상황, 즉 중국인의 나머지 정리가 적용되지 않는 경우에도 이용할 수 있다.

계속해서 『손자산경』의 문제를 생각해 보자. 3과 5 × 7 = 35, 5와 3 × 7 = 21, 7과 3 × 5 = 15는 각각 서로소이므로, 확장된 유클리드 호제법에 의해, (''m'', ''n'') = (3, 35), (5, 21), (7, 15) 각각에 대해, 부정 방정식

''mx'' + ''ny'' = 1

의 정수해(특수해)를 계산할 수 있다. 구체적으로는,

3 × 12 + 35 × (−1) = 1,

5 × (−4) + 21 × 1 = 1,

7 × (−2) + 15 × 1 = 1

이 된다. 따라서 다음 합동식이 성립한다.

－35 ≡ 1 (mod 3),

21 ≡ 1 (mod 5),

15 ≡ 1 (mod 7).

그러면 연립 합동식

''x'' ≡ ''a''₁ (mod 3),

''x'' ≡ ''a''₂ (mod 5),

''x'' ≡ ''a''₃ (mod 7)

의 하나의 해가

''x'' = −35''a''₁ + 21''a''₂ + 15''a''₃

임을 쉽게 확인할 수 있다. 게다가 정리에 의해 해는 3 × 5 × 7 = 105를 법으로 일의적이므로, 모든 해는 ''k''를 임의의 정수로 하여,

−35''a''₁ + 21''a''₂ + 15''a''₃ + 105''k''

로 표현된다는 것을 알 수 있다. 즉, 이것이 이 문제의 일반해이다.

5. 5. 선형 디오판토스 방정식 시스템

6. 응용

손자산경에 나오는 문제와 해답은 다음과 같다.

지금 물건이 있는데, 그 수를 알 수 없다. 3개씩 세면 2가 남고, 5개씩 세면 3이 남고, 7개씩 세면 2가 남는다. 물건은 몇 개인가?

답: 23

술법: 3개씩 세어 2가 남는 수로 140을 둔다. 5개씩 세어 3이 남는 수로 63을 둔다. 7개씩 세어 2가 남는 수로 30을 둔다. 이들을 더하면 233이 된다. 여기서 210을 빼면 답을 얻는다. 일반적으로 3개씩 세어 1이 남으면, 그때마다 70을 둔다. 5로 나눈 나머지에 21을 곱한다. 7로 나눈 나머지에 15를 곱한다. 106 이상이면 105를 빼면 답을 얻는다.

이 문제는 손자산경과 함께 일본에도 전해졌으며, 이후 와산이 융성했던 에도 시대에는 "백오감산"으로 알려졌다.

13세기 남송 말기의 수학자 진구소는 일차 합동식을 유클리드 호제법과 동등한 방법으로 풀어 중국인의 나머지 정리와 동등한 결과를 얻었다. 이 사실은 선교사에 의해 19세기 유럽에도 전해졌고, 가우스의 방법과 동등하다는 것이 확인되었다.

"Chinese remainder theorem^영어"이라는 이름은 적어도 미국의 수학자 레오나드 E. 딕슨의 저서 ''Introduction to the Theory of Numbers'' (1929)에서 찾아볼 수 있다.

중국인의 나머지 정리는 이 외에도 괴델 수의 수열을 구성하거나, 소인수 FFT 알고리즘 계산, RSA 암호화 방식 등에 사용된다. 비밀 공유나 중간 펄스 반복 주파수 레이더에서 사용되는 범위 모호성 해결 기술에도 응용된다.

6. 1. 수열 번호 매기기 (Sequence numbering)

중국인의 나머지 정리는 괴델 수의 수열을 구성하는 데 사용되었으며, 이는 괴델의 불완전성 정리 증명에 관여한다.^[1]

6. 2. 고속 푸리에 변환 (Fast Fourier Transform)

소인수 FFT 알고리즘(굿-토마스 알고리즘이라고도 함)은 크기

n_1n_2

의 고속 푸리에 변환 계산을 더 작은 크기

n_1

과

n_2

의 두 고속 푸리에 변환 계산으로 줄이기 위해 중국인의 나머지 정리를 사용한다(단,

n_1

과

n_2

는 서로소여야 함).

6. 3. 암호학 (Encryption)

RSA의 대부분 구현은 HTTPS 인증서 서명 및 복호화 과정에서 중국인의 나머지 정리를 사용한다.^[1]

중국인의 나머지 정리는 비밀 공유에도 사용될 수 있다. 비밀 공유는 일련의 공유물을 한 그룹의 사람들에게 분배하여, 그들 모두가 함께 (그러나 혼자서는 안 됨) 주어진 공유물 세트로부터 특정 비밀을 복구할 수 있도록 하는 것이다.^[1] 각 공유물은 합동식으로 표현되며, 중국인의 나머지 정리를 사용한 합동식 시스템의 해는 복구할 비밀이다.^[1] 중국인의 나머지 정리를 사용한 비밀 공유는, 중국인의 나머지 정리와 함께, 특정 기수 미만의 공유물 세트에서는 비밀을 복구하는 것이 불가능하도록 보장하는 특수한 정수 시퀀스를 사용한다.^[1]

6. 4. 범위 모호성 해결 (Range ambiguity resolution)

중간 펄스 반복 주파수 레이더에서 사용되는 범위 모호성 해결 기술은 중국인의 나머지 정리의 특수한 경우로 볼 수 있다.

7. 추가 확장

互素|후쑤^중국어가 아닌 법(moduli)으로 일반화될 수 있다. $m, n, a, b$ 를 정수, $g = \gcd(m,n)$ 을 최대공약수, $M = \operatorname{lcm}(m,n)$ 을 최소공배수라고 하고 다음 합동식 시스템을 고려해 보자.

: $\begin{align}x &\equiv a \pmod m \\x &\equiv b \pmod n,\end{align}$

만약 $a \equiv b \pmod g$ 이면, 이 시스템은 $M = mn/g$ 를 법으로 하는 유일한 해를 갖는다. 그렇지 않으면 해가 없다.

베주 항등식을 사용하여 $g = um + vn$ 으로 쓸 수 있다면, 해는 다음과 같다.

: $x = \frac{avn+bum}{g}.$

$g$ 가 $m$ 과 $n$ 모두를 나누므로, 이는 정수를 정의한다. 그렇지 않은 경우, 증명은 서로소 법에 대한 증명과 매우 유사하다.

환에 대한 서로소 이상 (또는 코맥시멀 아이디얼)을 사용하여 일반화될 수 있다. 두 개의 아이디얼 $I$ 와 $J$ 는 $i\in I$ 및 $j\in J$ 가 존재하여 $i+j=1.$ 을 만족하면 서로소이다. 이 관계는 이 일반화와 관련된 증명에서 베주 항등식의 역할을 하며, 그렇지 않으면 매우 유사하다. 일반화는 다음과 같이 나타낼 수 있다.^[16]^[17]

환 $R$ 의 양쪽 아이디얼을 $I_1, ..., I_k$ 라고 하고, $I$ 를 그들의 교집합이라고 하자. 아이디얼이 쌍별로 서로소이면, 다음의 동형이 성립한다.

: $\begin{align}R/I &\to (R/I_1) \times \cdots \times (R/I_k) \\x \bmod I &\mapsto (x \bmod I_1,\, \ldots,\, x \bmod I_k),\end{align}$

여기서 " $x \bmod I$ "는 아이디얼 $I$ 에 의해 정의된 몫환에서 원소 $x$ 의 상을 나타낸다.

또한, $R$ 이 가환이면, 쌍별로 서로소인 아이디얼의 아이디얼 교집합은 그들의 곱과 같다. 즉,

: $I= I_1\cap I_2 \cap\cdots\cap I_k= I_1I_2\cdots I_k,$

만약 모든 $i \neq j$ 에 대해 $I_i$ 와 $I_j$ 가 서로소이면.

참조

_[1] 서적
_[2] 서적
_[3] 서적
_[4] 서적
_[5] 서적
_[6] 서적
_[7] 서적
_[8] 서적
_[9] 서적
_[10] 서적
_[11] 서적
_[12] 서적
_[13] 서적
_[14] 서적
_[15] 서적
_[16] 서적
_[17] 서적
_[18] 서적
_[19] 서적 いくつかの与えられた法に関していくつかの与えられた剰余と合同な数の探索について
_[20] 서적 孫子算経
_[21] 문서 「三で割ると」の意。以下そのように訳す。
_[22] 문서 「三で割った余りに七十をかける」の意。以下そのように訳す。
_[23] 웹사이트 Earliest Known Uses of Some of the Words of Mathematics (C) http://jeff560.tripo[...] 2017-09-02
_[24] 문서 ここで、『''mn'' を法として一意的に存在する』とは次のような意味である。つまり、ある整数 ''y'' があって、この ''y'' も上の連立合同式の解であるならば、すなわち、
_[25] 서적
_[26] 서적
_[27] 서적

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com