안녕하세요. 플랫폼공작소입니다. 중국인의 나머지 정리(Chinese Remainder Theorem)에 대해서 알아보겠습니다.
1. 개요
중국의 5세기 문헌인 『손자산경(孫子算經)』에 등장한 문제. 서양사람들 입장에서 이 수학문제를 중국인이 만든건 아는데 대체 누가 만든지 몰라서 걍 "중국인의 나머지정리"라고 부른다고 한다.
2. 요약
중국인의 나머지 정리는 연립 합동식의 [해가 존재]한다는 것 + [그 해가 유일]하다는 것을 증명하는 정리이다. 예제를 보면 바로 이해될 것이다.
3. 예제1
예제에 합동식 표기가 나온다. 합동식을 모른다면, https://doctorson0309.tistory.com/732를 살짝 읽고 오자.
x ≡ 1 (mod 3) <- 해석 : x를 3으로 나누면 나머지가 1이다.
x ≡ 1 (mod 5) <- 해석 : x를 5으로 나누면 나머지가 1이다.
어라? 이러면 x를 15로 나눠도 나머지가 1인거 아냐? 맞다.
x ≡ 1 (mod 15) <- 15으로 나누면 나머지가 1이다. 이것이 성립하는 것을 증명하는 것이 중국인 나머지 정리이다.
4. 실전 문제 풀이
x ≡ 2 (mod 3)이고 x ≡ 4 (mod 5)일 때 x ≡ a (mod 15)가 있다고 가정하다. a의 값은 무엇인가?
4-1 해석, 실전 문제 풀이
x ≡ 2 (mod 3) <- 해석 : x를 3으로 나눴더니 2가 남더라. 아.. 1이 모자라다. 하나만 더 있으면 3의 배수인데..
x ≡ 4 (mod 5) <- 해석 : x를 5로 나눴더니 4가 남더라. 아.. 1이 모자라다. 하나만 더 있으면 5의 배수인데..
어라? 이러면 a를 구하는 치트키가 있잖아?
15에서 하나가 모자라겠지. 예를 들면 14같은 놈.
답 : a = 14
즉, x ≡ 14 (mod 15) 이다.
x ≡ a (mod 15) <- 1이 모자라다. 하나만 더 있으면 15의 배수인데..
추가로 질문사항이 있으시면 댓글 남겨주세요.
감사합니다. 좋은 하루 보내세요~
continue...
reference : https://www.youtube.com/watch?v=IBEloc4LC7o
광고 링크 : 플랫폼공작소, 플랫폼공작소TV, 쇼핑몰
