pseong

중국인의 나머지 정리가 무엇을 의미하는지는 나무위키에 잘 설명이 되어있다. 중국인의 나머지 정리 - 나무위키 (namu.wiki) 보통 중국인의 나머지 정리라 하면 모든 m이 서로소여야 한다. 하지만 서로소가 아닐때도 해를 구하고 싶을때가 있을 것이다. 이런 경우에는 두 개의 합동식을 하나로 합친다. 계속 이렇게 합쳐 주다가 마지막 한 개의 합동식만 남았을 때 답을 구해주면 해결된다. 따라서 두 개의 합동식을 합치는 방법만 알면 문제를 풀 수 있다. x ≡ a1 ( mod x1 ) x ≡ a2 ( mod x2 ) 먼저 이렇게 두 개의 합동식이 있다고 하자. g = gcd(x1, x2) 라고 하자. 아래 두 개의 식이 성립하므로 x ≡ a1 (mod g) x ≡ a2 (mod g) 다음 식이 성립한다고 할..