중국인의 나머지 정리

중국인의 나머지 정리(CRT: Chinese remainder theorem)를 이용하면 한 개의 변수와 서로소인 다른 모듈로를 갖는 합동 방정식의 해를 구할 수 있다. 이 방정식은 아래와 같이 표현된다.
$$
x \equiv a_1(mod\ m_1),\ x \equiv a_2(mod\ m_2),\ ...\ ,\ x \equiv a_3(mod\ m_3)
$$
중국인의 나머지 정리는 모듈로 값들이 서로소만 된다면 위의 연립 방정식이 유일한 해를 갖는다는 것을 보인 정리이다.

다음 연립 방정식의 해를 구하시오.
$$
x \equiv 2(mod\ 3),\ x \equiv 3(mod\ 5),\ x \equiv 2(mod\ 7)
$$
풀이

이 연립 방정식의 해는 다음 단계로 구할 수 있다.

1. 공통 모듈로로 사용할 $M = m_1 \times m_2 \times \ ... \ m_k$를 구한다.

2. $M_1 = M/m_1, \ M_2 = M/m_2, \ ...\ ,\ M_k = M/m_k$를 구한다.

3. 각각의 식에 대응하는 모듈로 값인 $(m_1,\ m_2,\ m_3)$를 이용하여 곱에 대한 역원인 $M_1,\ M_2,\ ...\ ,\ M_k$를 구한다. 각각의 역원을 $M_1\ ^{-1},\ M_2\ ^{-1},\ ...\ ,\ M_k\ ^{-1}$라고 나타낸다.

4. 이 연립 방정식의 해는 다음과 같다.
   $$
   x=(a_1\times M_1\times M_1\ ^{-1} + a_2\times M_2\times M_2\ ^{-1}+\ ...\ +a_k\times M_k\times M_k\ ^{-1})\ mod\ M
   $$

다음 4단계에 따라 해를 구해보자.

1. $M=3\times 5\times 7 = 105$이다.
2. $M_1=105/3=35,\ M_2=105/5=21,\ M_3=105/7=15$이다.
3. 곱에 대한 역원은 $M_1\ ^{-1}=2,\ M_2\ ^{-1}=1. M_3\ ^{-1}=1$이다.
4. $x=(2\times35\times2+3\times21\times1+15\times1)\ mod\ 105=23\ mod\ 105$

곱셈에 대한 역원

$Z_n$에서 두 수 $a,\ b$는 다음을 만족하면 서로 곱셈에 대한 역원이 된다.
$$
a\times b\equiv 1\ mod\ n
$$
예를 들어, 모듈로가 $10$이면 $3$의 곱셈에 대한 역원은 $7$이다. 즉, $(3 \times 7)\ mod\ 10=1$이다.

모듈로 연산에서 정수는 곱셈에 대한 역원이 있을수도 있고 없을수도 있다.
만약 곱셈에 대한 역원이 있다면, 
그 정수와 해당하는 곱셈에 대한 역원의 곱은 모듈로 n에서 1과 합동이다.

$a$가 $Z_n$에서 곱셈에 대한 역원을 갖기 위한 필요충분조건이 $gcd(n,a)=1$이라는 것을 증명 할 수 있다.

이 경우 $a$와 $n$은 서로소라고 한다.

[명제] 필요조건, 충분조건, 필요충분조건

명제 $P \rightarrow Q$는 가정인 $P$와 결론인 $Q$로 정의할 수 있다.

명제 $P \rightarrow Q$가 참이면

$$
P \Rightarrow Q
$$

로 표현할 수 있다.

이때 조건 $P$는 $Q$이기 위한 충분조건이라하고, 조건 $Q$는 조건 $P$이기 위한 필요조건이라 한다.

만약 $P \Rightarrow Q$이면서 $Q \Rightarrow P$이면

$$
P \Leftrightarrow Q
$$

로 표현할 수 있다.

이때 조건 $P$는 $Q$이기 위한 필요충분조건이라하고, 마찬가지로 조건 $Q$는 조건 $P$이기 위한 필요충분조건이라 한다.