Processing math: 100%

정의

중국인의 나머지 정리(Chinese remainder theorem; CRT)는 중국의 5세기 손자산경에 나오는 문제로 다음과 같다.

3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가?


이를 수식으로 자세히 정리하면 아래와 같다.

서로 서로소인 음이 아닌 정수 k개가 있다고 가정하자. gcd(ni,nj) = 1 (i j)
n1,n2,...,nk 
n =ki=1ni

그렇다면 다음 연립 합동 방정식의 해 aZ/n 는 항상 유일하게 존재한다.

aa1 (mod n1)
aa2 (mod n2)
...
aak (mod nk)

 

증명

이 고대 수학 정리는 언뜻 간단해 보이지면 증명을 위해 여러 보조정리가 필요하다.

많은 글에서 보조정리를 나열하여 다루지만 이 글에서는 문제 본연의 풀이에 집중하기 위해 해의 존재성유일성 각각에 맞춰 풀이한다.

 

존재성

존재성은 위 연립 합동 방정식을 만족하는 해 xZ/n (쉽게 0x<n 인 정수) 가 존재함을 증명하면 된다. 확장된 유클리드 호제법 등 많은 정수론에서 해를 구하기 위해 혹은 존재성을 입증하기 위해 베주 항등식을 인용한다.

베주 항등식

a,bZ (a0 or b0)gcd(a,b)=d 이면

d=au+bv 를 만족하는 u,vZ 가 존재한다.

자세한 증명은 링크를 참조바라며 직관적인 이해는 아래와 같다.
최대공약수 d는 a, b의 특정 배수의 합으로 만들 수 있다는 것이다.
이를 확장한 증명으로 d는 a, b 배수 집합의 가장 작은 양의 정수다. 그리고 d의 배수들로 이 집합을 구성할 수 있다.
즉, a와 b로 나타낼 수 있는 정수 집합은 가장 기본 단위가 d라는 뜻 이다.

 

나머지 정리의 각 ni 에 대해 ni,nni 를 베주항등식 a,b 에 대입해보자.

 ni,nni 는 서로 서로소 이므로  gcd(ni,nni)=1

그렇다면 niui+nnivi=1 을 만족하는 ui,viZ가 존재한다.

여기서 ei=nnivi 라고 하면 아래 두 식이 성립한다.

ei1 (mod ni)
ei0 (mod nj, ij)

결국 각 ei 를 구하는 과정은 mod ni 시  nj (ij) 에 영향을 받지 않는 값을 구하기 위함이며 이를 모두 합한 a는 위 문제 해답 중 하나이다.

a=ki=1aiei

 

유일성

증명을 위해 반례로 x,yZ/n 두 해가 존재한다고 가정하자. 

그렇다면 모든 ni 에 대해 xyai (mod ni) 를 만족하므로 xy 는 모든  ni의 배수이다.

ni, nj (ij)는 서로소라고 가정 했으므로 모든 ni의 배수는 n의 배수이기도 하다.

즉, xyn의 배수라서 Z/n 에서 두 해가 존재할 수 없다.

 

응용

작업 중...

ei 를 구하는 방법: 유클리드 호재법 확장 vs 오일러 정리

반응형

'정수론' 카테고리의 다른 글

오일러 정리[Euler's Theorem]  (0) 2018.01.09
페르마의 소정리[Fermat's little theorem]  (0) 2017.12.23

+ Recent posts