중국인의 나머지 정리(CRT;Chinese Remainder Theorem)

 

🙆🏽‍♀️ 언젠가 한 번은 정확히 정리하고, 숙지해야 할 알고리즘 '중국인의 나머지 정리'

 

🙆🏽‍♀️ 이론을 정확히 알고, 여러 수학 문제에 적용해 복잡한 문제를 쉽게 풀어보자

---

합동식

🙆🏽‍♀️ 대수학에서 합동인 두 수는, 어떤 수로 나누었을 때 나머지가 같은 두 수를 뜻한다.

 

→ ex) 예를 들어 12와 26은 7로 나누었을 때 나머지가 5이므로 아래와 같은 기호로 쓸 수 있다.

$$12\equiv 26\;(mod\;7)$$

🙆🏽‍♀️ 즉, a를 p로 나눈 나머지와 b를 p로 나눈 나머지가 같다면,

$$a\equiv b\;(mod\;p)$$

🙆🏽‍♀️ 이를 식으로 표현한다면,

$a=pn+b$

* 합동식의 성질

① 덧셈은 언제나 성립 (동일한 수를 더하면 동일한 수의 나머지는 당연히 동일하므로 성립)

$$a \equiv b\;(mod \; m) \Leftrightarrow a+c\equiv b+c\;(mod\;m)$$

 

② 즉 뺄셈도 성립 (위에서 c를 빼면 된다)

 

③ 곱셈도 언제나 성립 (동일한 수를 곱하면 

$$a \equiv b\;(mod \; m) \Leftrightarrow a*c\equiv b*c\;(mod\;m)$$

→ 증명

$$a \equiv b\;(mod\;m)\Leftrightarrow c*m+d\equiv e*m+d\;(mod\;m)$$

양 변에 k배를 더하면

$$c*m*k+d*k\equiv e*m*k+d*k\;(mod\;m)\Leftrightarrow a*k\equiv b*k\;(mod\;m)$$

 

④ 나눗셈은 c와 m이 서로소이면 성립

$$a*c\equiv b*c\;(mod\;m)\Leftrightarrow a\equiv b\;(mod\;m)$$

 

⑤ modular까지 나눈다면 무조건 성립

$$a*c\equiv b*c\;(mod\;m*c)\Leftrightarrow a\equiv b\;(mod\;m)$$

중국인의 나머지 정리

🙆🏽‍♀️ 정의

 "$m_1, m_2, ... , m_n$가 쌍마다 서로소이면, 다음 연립 합동식

$$x\equiv a_1\;(mod\;m_1)$$

$$x\equiv a_2\;(mod\;m_2)$$

...

$$x\equiv a_n\;(mod\;m_n) $$

은  $mod\; m_1\ast m_2 \ast ... \ast m_n$에 대해 유일한 해를 가진다."

 

🙆🏽‍♀️ 중국인의 나머지 정리 위 합동식에 대해 유일성 & 존재성은 증명되었으니, 해당 해를 찾는 알고리즘을 알아야 한다

(중국인의 나머지 정리 증명 생략)

 

🙆🏽‍♀️

① n=2인 경우 해를 찾을 수 있다면, n > 2인 경우는 쉽게 해결 가능

② n>2인 경우 해의 존재 여부도 n=2인 경우만 할 수 있으면 판별 가능

n=2인 경우

🙆🏽‍♀️ n=2에 주목하면

→ $m_1, m_2$가 서로소이면 다음 연립 합동식

$$x\equiv a_1\;(mod\;m_1)$$

$$x\equiv a_2\;(mod\;m_2)$$

은 $mod \; m_1m_2$에 대해 유일한 해를 가진다.

 

🙆🏽‍♀️ 위 연립 합동식을 풀어 쓰면

$$x \equiv a_1(mod\;m_1) \leftrightarrow x = m_1y+a_1$$

두 번째 식과 연립하면 ($m_1, m_2$가 서로소일 때)

$x = m_1y + a_1 \equiv a_2 (mod \; m_2) \Leftrightarrow y \equiv (m_1)^{-1}(a_2 - a_1) (mod \; m_2)$

($m_1^{-1}$은 $mod \; m_2$에 대한 곱셈의 역원)

 

$t = (m_1)^{-1}(a_2 - a_1)$로 두면,

$y = m_2n + t$꼴이고, $x = m_1y + a_ 1 = m_1m_2n + m_1t + a_1$

 

따라서,

$x \equiv m_1t + a_1 (mod \;m_1m_2)$

 

🙆🏽‍♀️ 만약, $m_1, m_2$가 서로소가 아닐 경우

두 번째 식과 연립하면 ($m_1, m_2$가 서로소일 때)

$x = m_1y + a_1 \equiv a_2 (mod \; m_2) \Leftrightarrow m_1y \equiv a_2 - a_1 (mod \; m_2)$

 

이는 아래와 같이 나타낼 수 있고,

$m_1y = m_2k + (a_2 - a_1)$

 

$m_1, m_2$는 서로소가 아니므로 각각 $gcd(m_1,m_2)$의 배수

따라서, 위의 y가 존재 ↔ $a_2 - a_1$이 $gcd(m_1,m_2)$의 배수

 

따라서, 양변을 $gcd(m_1,m_2)$로 나누면 (modular 포함)

$m_1y \equiv a_2 - a_1 (mod\;m_2) \Leftrightarrow (m_1/gcd(m_1,m_2))y \equiv (a_2 - a_1)/gcd(m_1,m_2)\;(mod\;m_2/gcd(m_1,m_2))$

 

🙆🏽‍♀️ 결과적으로 $m_1, m_2$가 서로소인 경우와 식이 같아짐을 알 수 있다.

예시

① 

$$x \equiv 4\;(mod\;20)$$

$$x \equiv 5\;(mod\;24)$$

 

→ $x = 20y +4$를 두 번째 합동식에 대입

→ $20y +4 \equiv 5\;(mod\;24) \Leftrightarrow 20y \equiv 1\;(mod\;24)$

→ $20y = 24k + 1$로, 해가 존재하지 않음

 

②

$$x \equiv 11\;(mod\;20)$$

$$x \equiv 15\;(mod\;24)$$

 

→ $x = 20y +11$를 두 번째 합동식에 대입

→$20y +11 \equiv 15\;(mod\;24) \Leftrightarrow 20y \equiv 4\;(mod\;24)\Leftrightarrow 5y \equiv 1\;(mod\;6) \Leftrightarrow y \equiv 5\;(mod\;6)$

→ $y = 6k + 5$ 대입하면 $x = 20y + 11 = 20(6k + 5) + 11 = 120n + 111$

→ $x \equiv 111\;(mod\;120)$

 

③ 중국인의 나머지 정리 예시

→ 주어진 세 개의 연립 합동식을 만족하는 x를 구한다

$$x \equiv {\color{Red} 2}\;(mod\;3)$$

$$x \equiv {\color{Red} 3}\;(mod\;5)$$

$$x \equiv {\color{Red} 2}\;(mod\;7)$$

↓

→ 각 합동식에서 다른 modular들을 곱한다. (합동식의 결과는 모두 1로 설정)

$${\color{Red} {35}}*x_1 \equiv 1\;(mod\;3)$$

$${\color{Red} {21}}*x_2 \equiv 1\;(mod\;5)$$

$${\color{Red} {15}}*x_3 \equiv 1\;(mod\;7)$$

↓

→ 구한 합동식을 알맞게 푼다.

$$x_1 \equiv {\color{Red} 2}\;(mod\;3)$$

$$x_2 \equiv {\color{Red} 1}\;(mod\;5)$$

$$x_3 \equiv {\color{Red} 1}\;(mod\;7)$$

↓

→ 각각 빨간색의 숫자를 합동식별로 곱한 뒤 더한 결과가 모든 modular를 곱한 값과 합동

$$x \equiv 2*35*2 + 3*21*1 + 2*15*1 \equiv 233 \equiv {\color{Red} {23}}\;(mod\;105)$$

---

* 출처1) <합동식> https://m.blog.naver.com/a4gkyum/220676133854

* 출처2) kaist <중국인의 나머지 정리> https://youtu.be/mOYl_pkNEAE

* 출처3) KMO 바이블 <중국인의 나머지 정리> https://youtu.be/5vQsSBK60Vk

* 출처4) blog https://blog.naver.com/kks227/221635322468