본문 바로가기

Chinese Remainder Theorem

Chinese Remainder Theorem x ≡ 25 (mod 42)라는 수가 주어졌다고 하자. x를 결정하는 수를 대수로 풀어쓴다면, x = 25 + 42k라고 할 수 있을 것이다. 여기서 42k를 서로소인 두 수로 분해해본다면, (6, 7), (14, 3)과 같은 수가 있을 것이다. 즉, x = 25 + 6 * 7k, x = 25 + 14 * 3k라고 할 수 있다. 이것은, x ≡ 4 (mod 7), x ≡ 1 (mod 6)과 같은 형태로 다시 쓸 수 있는데, 여기서 중요한 것은 이 두 수가 서로소여야 한다. 만약, 두 수가 서로소가 아니라면, 이 합동식은 같은 나머지를 가지는 수로 나누었을 때 다른 나머지가 나온다는 모순이 생기기 때문이다. x ≡ 25 (mod 42)는, x ≡ 4 (mod 7), x ≡ 1 (mod 6)의 형태로 다시 .. 더보기

티스토리툴바