중국인의 나머지 정리
알림
|
페이지 정보
작성일
2024.08.29 13:23
본문
아래 글에는 풀이를 생략해서 적다보니 문제가 제대로 전달이 안된것 같네요.
찾아보니 흥미로워서
한번 소개해보겠습니다
세개씩 세면 2개가 남고
다섯개씩 세면 3개가 남고
일곱개씩 세면 2개가 남는다.
이 물건의 갯수는 몇개인가 (여기까지가 아래글)
풀이
세개씩 세면 1개가 남을 때는 70을 적는다
다섯씩 세어 1개가 남으면 21을 적는다
일곱씩 세어 1개가 남으면 15를 적는다
더한값이 106을 넘으면 그 값에서 105를 뺀다
다시 문제로 돌아가 세개씩 세어 2개가 남으니 70*2 = 140
다섯씩 세어 3개가 남으니 21*3 = 63
일곱씩 세어 2개가 남으니 15*2 = 30
합이 233 이니까 105를 2번 빼서 답은 23 입니다.
다른 예
세개씩 세어 2개가 남고
다섯씩 세어 4개가 남고
일곱씩 세어 5개가 남으면
70*2+21*4+15*5 = 299 이고 210을 빼면 89 가 정답이겠네요.
중국인의 나머지 정리의 핵심은
왜 70, 21, 15, 105 인가 겠구요 ㅎㅎ
-
07:24
댓글 10
/ 1 페이지
커피믹스는에스프레소의꿈을꾸는가님의 댓글
105야 최소공배수고요
106을 70 21 15로 쪼갠거같은데...(까지 쓰고 좀더 생각해보겠음다)
106을 70 21 15로 쪼갠거같은데...(까지 쓰고 좀더 생각해보겠음다)
담임선생님의 댓글
엑셀로 풀었습니다.
정답은 X로 놓고 배수는 각 a, b, c로 놓았을 때, 모든 X/a/b/c가 자연수가 되는 조건이군요
정답은 X로 놓고 배수는 각 a, b, c로 놓았을 때, 모든 X/a/b/c가 자연수가 되는 조건이군요
메이데이님의 댓글
중국인의 나머지 정리라고 해서 문화대혁명이나
시진핑의 정적 암살인지 알고 들어왔네요..ㅋ
시진핑의 정적 암살인지 알고 들어왔네요..ㅋ
규링님의 댓글
무식해서 그냥 방정식 대입하고 성립 조건 찾아서 풀었는데
써주신 글에 나온 저 숫자들이 왜 나온건지는 모르겠네요.
일리어스님의 댓글의 댓글
@규링님에게 답글
저 숫자가 나오게 되는 이유가 나머지정리라고 할수 있는건데요
주어진 서로소의 갯수와 상관없이.(이 문제에서는 3개)
서로소인 a,b,c 로 나누었을 때 p,q,r 이 나머지인 자연수는 다음과 같은 식으로 표현 가능하다는겁니다.
Ap + Bq + Cr + N * abc
여기서 대문자 ABC는 각각 다른 두수로는 나누어떨어지면서 다른 한수로 나누면 1 만 남는 수.
문제에서는 70, 21, 15 가 되는거죠.
N은 그냥 정수구요.
그래서 저 식에 대입하면
70*2 + 21*3 + 15*2 + N*105 형태의 자연수를 구하면 그 수는 저 식을 모두 만족하게 된다는거죠.
이게 처음 실린게 3세기 중국 수학책이였다고 합니다.
주어진 서로소의 갯수와 상관없이.(이 문제에서는 3개)
서로소인 a,b,c 로 나누었을 때 p,q,r 이 나머지인 자연수는 다음과 같은 식으로 표현 가능하다는겁니다.
Ap + Bq + Cr + N * abc
여기서 대문자 ABC는 각각 다른 두수로는 나누어떨어지면서 다른 한수로 나누면 1 만 남는 수.
문제에서는 70, 21, 15 가 되는거죠.
N은 그냥 정수구요.
그래서 저 식에 대입하면
70*2 + 21*3 + 15*2 + N*105 형태의 자연수를 구하면 그 수는 저 식을 모두 만족하게 된다는거죠.
이게 처음 실린게 3세기 중국 수학책이였다고 합니다.
규링님의 댓글의 댓글
@일리어스님에게 답글
오호, 그렇군요. 나머지정리 자체가 또 다른 방법인 것이군요.
하나 배워갑니다.
하나 배워갑니다.
kita님의 댓글