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