Chinese Remainder Theorem

나는 야호다.

오늘은 중국인의 나머지정리에 대해 배워보자.

$$
\begin{aligned}
x &\equiv a_1 \pmod {m_1} \\
x &\equiv a_2 \pmod {m_2} \\
...\\
x &\equiv a_n \pmod {m_n}
\end{aligned}
$$

이런 문제를 푸는데 유용한 방법인 것이다.

중국인의 나머지 정리는 다음과 같다.

$$m_i$$가 모두 쌍마다 서로소라면, 위의 일차연립합동방정식은 $$\pmod {m_1m_2...m_n}$$에 대해서 유일한 해를 갖는다.

증명이 곧 문제 풀이 방법이니 이를 설명하도록 하겠다.

$$m=m_1m_2...m_n$$이라 하자. 그러면 우리는 다음을 찾는 것이 된다.

$$x\equiv \sum a_ix_i \pmod m$$를 만족하는 $$x_i$$들을 찾으면서 각각의 $$x_i$$들이 다음을 만족하면 된다.

$$x_i \equiv 1 \pmod {m_i}$$ , $$x_i \equiv 0 \pmod {m_j} (i \neq j)$$

2번째 조건을 만족하려면 $$x_i$$는 $$mod m$$에서 $$m_i$$를 제외하고 나머지 $$m_j$$에 대해서는 배수 관계에 있어야 되므로 다음과 같이 나타낼수 있다.

$$x_i \equiv \frac{m}{m_i}s_i \pmod m$$

또한 첫번째 조건인 $$x_i \equiv 1 \pmod {m_i}$$가 만족해야 한다.

그런데 $$gcd(\frac{m}{m_i}, m_i)=1$$이므로 $$\frac{m}{m_i}s_i \equiv 1 \pmod {m_i}$$인 $$s_i$$를 항상 찾을 수 있다.

이에 대해서는 https://panty.run/egcd/ 참고.

따라서 $$x \equiv \sum a_i \frac{m}{m_i} s_i \pmod m$$이 우리가 찾고자 하는 해가 된다.

자 서로소가 아닐때는 이제 어떻게 할까?

필자는 $$n$$개를 한꺼번에 처리하는 방법은 모르고 두개씩 밖에 못한다. 하지만 괜찮다. 두개씩 하면 된다.

$$
\begin{aligned}
x &\equiv a_1 \pmod {m_1} \\
x &\equiv a_2 \pmod {m_2} \\
\end{aligned}
$$

라는 식이 있다고 하자. 첫번째 식에서 $$x=m_1k_1+a_1$$이 만족하므로 이를 두번째 식에 대입하면 $$m_1k_1 \equiv a_2-a_1 \pmod {m_2}$$가 성립하게 된다. 확장유클리드 호제법에 의해서, $$a_2-a_1$$이 $$gcd(m_1,m_2) $$의 배수일 경우에만 이 식을 만족하는 해가 존재하게 된다. 따라서 다음이 성립해야 된다.

$$a_1\equiv a_2 \pmod {gcd(m_1,m_2)}$$

이를 이용해서 2개씩 계산하면 $$n$$개일 때도 계산할수 있다.

이상이다.