CRT (1) 썸네일형 리스트형 52. Chinese Remainder Theorem 정수론에서 중국인의 나머지 정리(Chinese Remainder Theorem, CRT)는 서로소인 $n$개의 양의 정수 $m_1, m_2, \ldots, m_n$과 $0 \le a_i < m_i$ $(1 \le i \le n)$를 만족하는 $n$개의 정수 $a_1, a_2, \ldots a_n$에 대해 다음 $n$개의 합동식 $$x \equiv a_i \pmod{m_i} \quad (1 \le i \le n)$$ 을 모두 만족하는 $0$ 이상 $\prod_{i = 1}^n m_i$ 미만의 정수 $x$가 유일하게 존재한다는 정리이다. 이 정리의 역사는 $5$세기로 거슬러 올라간다. 중국 남북조 시대의 수학서인 『손자산경』에는 다음과 같은 문제가 등장하는데, 이것이 중국인의 나머지 정리가 처음으로 등장하는.. 이전 1 다음
