관리 메뉴

플랫폼공작소 IT Blog

[정수론] 5분 만에 중국인의 나머지정리 이해하기 본문

플랫폼공작소 언론사/일상 꿀팁 공유소

[정수론] 5분 만에 중국인의 나머지정리 이해하기

솜픽(Sompic) 플랫폼공작소 2020. 5. 13. 00:51


안녕하세요. 플랫폼공작소입니다. 중국인의 나머지 정리(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쇼핑몰




0 Comments
댓글쓰기 폼