본문 바로가기

Daylogs/Logic

중국인의 나머지 정리

발생일: 2009.06.30

문제:
구글 코드잼 문제를 풀다보니, 중국인의 나머지 정리(Chinese remainder theorem)가 적용되어야 했다.
중국인의 나머지 정리라... 당췌 이게 뭔지 모르겠다.... -_-a.

해결책:
중국인의 나머지 정리에 대해 쉽게 정리해 둔 블로그가 있다.
어느 정도 감이 잡히기는 하는데,...
아직 잘 모르겠다. @_@

10 이하의 소수 중 하나(2 또는 3, 5, 7)로 나눠지는 수 x 가 있다.
근데 이 x의 수가 꽤 크다면, 아래와 같이 계산한 x' 도 10 이하의 소수 중 하나로 나눠진다고 한다.

x' = x MOD (2 * 3 * 5 * 7)

왜 그런 걸까...... -_-a
알려주세요....


* 팁: 수학사랑 사이트에서 주요 수학 정리에 대해 잘 설명해두었다.