잉여의 생각저장소

정의

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

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

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

서로 서로소인 음이 아닌 정수 k개가 있다고 가정하자. gcd($n_{i}, n_{j}$) = 1 (i $\neq$ j)
$n_{1}, n_{2}, ..., n_{k}$ 
$n \ = \prod_{i=1}^k n_{i}$

그렇다면 다음 연립 합동 방정식의 해 $a \in \mathbb{Z}/n$ 는 항상 유일하게 존재한다.

$a \equiv a_{1} \ (mod \ n_{1})$
$a \equiv a_{2} \ (mod \ n_{2})$
...
$a \equiv a_{k} \ (mod \ n_{k})$

증명

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

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

존재성

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

베주 항등식

$ a,b \in \mathbb{Z} \ (a \neq 0 \ or \ b \neq 0)$,  $gcd(a, b)=d$ 이면

$ d = au + bv $ 를 만족하는 $ u, v \in \mathbb{Z} $ 가 존재한다.

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

나머지 정리의 각 $n_{i}$ 에 대해 $ n_{i}, \frac{n}{n_{i}} $ 를 베주항등식 $ a, b $ 에 대입해보자.

 $n_{i}, \frac{n}{n_{i}}$ 는 서로 서로소 이므로  $gcd(n_{i}, \frac{n}{n_{i}}) = 1$

그렇다면 $n_{i}u_{i} + \frac{n}{n_{i}}v_{i} = 1$ 을 만족하는 $u_{i}, v_{i} \in  \mathbb{Z} $가 존재한다.

여기서 $e_{i} = \frac{n}{n_{i}}v_{i}$ 라고 하면 아래 두 식이 성립한다.

$e_{i} \equiv 1\ (mod\ n_{i})$
$e_{i} \equiv 0\ (mod\ n_{j},\ i \neq j)$

결국 각 $e_{i}$ 를 구하는 과정은 $mod\ n_{i}$ 시  $n_{j}\ (i \neq j)$ 에 영향을 받지 않는 값을 구하기 위함이며 이를 모두 합한 a는 위 문제 해답 중 하나이다.

$a = \sum_{i=1}^ka_{i}e_{i} $

유일성

증명을 위해 반례로 $ x, y \in \mathbb{Z}/n $ 두 해가 존재한다고 가정하자. 

그렇다면 모든 $n_{i}$ 에 대해 $ x \equiv y \equiv a_{i}\ (mod\ n_{i}) $ 를 만족하므로 $x-y$ 는 모든  $n_{i}$의 배수이다.

각 $ n_{i},\ n_{j}\ (i \neq j) $는 서로소라고 가정 했으므로 모든 $n_{i}$의 배수는 $n$의 배수이기도 하다.

즉, $x-y$ 는 $n$의 배수라서 $ \mathbb{Z}/n $ 에서 두 해가 존재할 수 없다.

응용

작업 중...

$e_{i}$ 를 구하는 방법: 유클리드 호재법 확장 vs 오일러 정리

정의

페르마의 소정리를 일반화 한 것이다.

임의의 자연수 a, n이 서로소일 때 아래 식을 만족한다.

여기서 φ(n)은 오일러의 피 함수라 하며 1 부터 n까지의 자연수 중에 n과 서로소인 것의 개수를 나타내는 함수이다.

증명

오일러 정리 증명 과정은 이전에 포스팅 한 페르마의 소정리의 증명과 유사하다.

① 아래 집합 S는 n이하 자연수에서 n과 서로소인 수들의 집합이다.

심화

오일러 정리 증명과정이 페르마의 소정리의 증명과 유사하여 왜 굳이 φ(n) 오일러의 피 함수가 필요한지 의문이 들 수 있다.

실제로 φ(n)은 n이 소수가 아니면 계산량이 많아 나머지 연산에서 n이 소수일 때가 많다.

그럼 모든 자연수 a, n이 서로소일 때 페르마의 소정리의 식을 증명하도록 유도해보자.

① 아래 집합 S는 n보다 작은 자연수들의 집합이다.

③ 페르마의 소정리의 증명 ①을 통해 S = AS 이다.

④ 두 집합의 곱이 합동이다. (여기까지는 오일러 정리와 같으며 참이다.)

⑤ 1 ~ n-1 중 n과 서로소가 아닌 수는 나눌 수 없다.

모든 정수 a, b에 대해 a*c ≡ b*c (mod n) 일 때 a ≡ b (mod n)을 만족하려면 n과 c가 서로소여야 한다.

a*c ≡ b*c, (a-b)*c ≡ 0 (mod n) 이다. 이 때 c가 n과 서로소가 아닌 n의 약수라면 a-b가 n의 다른 약수일 때

(a-b)*c ≡ 0 (mod n) 이 식은 만족한다.

예를 들어 4*2 ≡ 1*2 (mod 6)은 만족하지만 4 ≡ 1 (mod 6)은 아니다.

위 과정을 통해 mod n에서 n이 소수가 아닐 때 페르마의 소정리 식이 만족하지 않으며 φ(n)을 계산해야하는 이유를 알 수 있다.

그리고 n이 소수일 때 n보다 작은 모든 자연수는 n과 서로소이므로 φ(n) = n-1이다.

rsa 암호에서 쓰이는 소수들의 곱으로 나머지 연산을 하는 경우, 서로 다른 소수 p, q에 대해 φ(p*q) = (p-1)*(q-1) 로 응용해서 쓸 수도 있다.

응용

큰 지수 제곱을 나머지 연산에서 구하는 문제를 쉽게 풀 수 있다.

마치며

 이번시간에는 페르마의 소정리와 오일러 정리가 어떻게 다른지 오일러 피 함수가 왜 필요한지를 말씀드렸습니다.

다음시간에는 조합론에서 이용되는 뤼카의 정리를 포스팅할 까 합니다~

정의

소수인 p와 정수인 a가 서로 서로소일 때 아래의 식을 만족한다.

증명

①  a, 2a, 3a, ..., (p-1)a 인 p-1 개의 수들이 p로 나눈 나머지가 모두 다르다.

→ (귀류법으로 참임을 증명)

  ①번 명제가 거짓이라면 서로 같은 나머지를 가진 두 수 i*a, j*a (0<i<j<a)의 차를 p로 나누었을 때 나누어 떨어지는 경우의 수가 있어야 한다.

  하지만 두 수의 차는 (j-i)*a 이며 a는 p와 서로소이고 1 < j-i < p 이므로 위와 같은 경우의 수는 없다. 따라서 ①번 명제는 참이다.

② 집합 A = { x | x = i*a, i ∈ { 1, 2, ..., p-1} }는 ①에 따라 나머지가 모두 다르다. 따라서 A는 집합 B = {1, 2, ..., p-1} 와 원소의 수 및 값이 같으니 다음을 증명한다.

따라서 위 정의는 a와 p가 서로소일 때 참이다.

③ 모든 정수 a에 대해선 아래 식을 만족한다. (②에서 a와 p가 서로소일 때 증명하였고, a가 p의 배수일 때 a ≡ 0 (mod p) 이므로)

응용

페르마의 소정리를 응용하면 아래의 식을 만들 수 있다. 이를 이용하면 mod p에서 모든 정수형 나눗셈을 정수형 곱셈으로 치환 가능하다.

예를들어 nCr (mod p) 를 구할 때 모두 자연수의 곱셈으로 표현이 가능하다. (백준 이항계수2, https://www.acmicpc.net/problem/11051)

마치며

처음으로 포스팅하며 학생때 관심을 많이 가졌던 정수론 부터 정리하고 있습니다. 사실 nCr (mod p)을 빠르게 구하려면 뤼카의 정리를 이용합니다.

다음시간에는 오일러의 정리와 이어서 이 둘로 증명과정을 거쳐 만들어진 RSA 알고리즘에 대해 포스팅 할까 합니다.