- 중국인의 나머지 정리-
물건의 개수를 모른다. 하지만 우리는 아래의 정보를 알고 있다.
3으로 나눈 나머지는 1이고 5로 나눈 나머지는 1이며 7로 나눈 나머지는 2이다.
물건의 개수는 몇개인가??
지구상 풀지못하는 최고의 난제인줄 알았다.
답 : 16
물론 수가 작아서 1부터 해보면 16을 쉽게 찾을 수도 있지만 수가 크다면 일일히 해보는 방법은
수학적으로도 무식한 방법일 것이다.
인터넷을 돌아다니다 얻은 풀이방법들이다.
< 첫번째 풀이방법>
1. 3으로 나누면 1이 남는 식을 3x+1라고 한다.
2. x의 범위는 0부터 시작이므로 1,4,7,9,13,16,19,22,25,28,31....
3. 여기서 5로 나눈 나머지가 1인 수들을 찾는다. 1,16,31....
4. 이 수중에서 7로 나눈 나머지가 2인 수들을 찾는다.
16을 7로 나눈 나머지가 2이므로 제일 작은 수는 16임을 알 수 있다.
<두번째 풀이방법>
1. 3으로 나눈 나머지가 1인 수를 3x+1
2. 5로 나눈 나머지가 1인 수를 5x+1
3. 7로 나눈 나머지가 2인 수를 7x+2라고 한다.
3x+1=5x+1=7x+2=k 로 놓는다.
여기서 3x+1=5x+1=k 식에서 -1을 빼주면
3x=5x=k-1로 k-1은 3의 배수이면서 5의배수이므로
k-1= 15일 때 최소이다.
k=16 임을 알 수 있다.
4. 마지막으로 16을 7로 나누었을 때 나머지가 2인지 확인한다.
첫번째 풀이는 가장 큰 수인 7을 이용해서 푸는게 더 간편하다고 한다.
9,16,23..이므로 두번만에 답을 구할 수 있다.
그러나 가장 큰 수를 이용하여 풀어도 더 복잡한 문제에서 이 방법은 오래걸릴 것이다.
두번째 풀이는 나머지가 같을 경우에만 사용할 수 있기에 보편적인 방법이라 할 수 없다.
블로그를 탐방하던 중 한시 한편으로 이 문제를 설명해 놓은 블로그를 발견했다. (정리 정말 잘하셨다 )
조선 시대 경선징의 <묵사집산법> ?? 이라는 칠언 절구의 한시라는데...
3인이 70세까지 함께 가기는 드문데
5마리의 봉새가 21일 전에 깃들인다.
7월의 가을바람이 십오[15]야에 일고
동지에서 한식까지는 105일 이러라.
신기하게도 이 시의 모든 수는 의미가 있다.
70은 5,7의 공배수 중에서 3으로 나누면 나머지가 1인 가장 작은 수
21은 3,7의 공배수 중에서 5로 나누면 나머지가 1인 가장 작은수
15는 3,5의 공배수 중에서 7로 나누면 나머지가 1인 가장 작은수
105는 3,5,7의 최소 공배수 이다.
와우!! 고대 사람들은 정말로 우리보다 똑똑한 것 같다.
이 문제를 풀기 위해서는 70*1 + 21*2+ 15*3 = 70+42+45=157
157 - 105 =52 임을 알 수 있다. 그런데 70,21,15에 각각 1,2,3을 곱해 주었고 그 값에서
3,5,7의 최소공배수를 왜 빼주었을까??????????????????????????????????????
이 문제는 고대의 역법 계산과 깊은 관련이 있다. 당시 천문학자들은 장기간에 걸친 천문관측 기록에 의거해서
해와 달 및 다섯 행성의 운동 주기를 추산하고, 이들 천체의 주기 운동의 기점, 즉 상원을 정할 필요가 있었다.
결국 서양 수학자들의 관심도 끌게 되었고, 위대한 수학자 오일러는 1734년에 러시아의 한 잡지에 다음과 같이 기술했다.
서로 소인 다섯 개의 수 a,b,c,d,e로 나눌 때의 나머지가 차례로 p,q,r,s,t인 자연수는 다음과 같다.
Ap + Bq + Cr + Ds + Et + m x abcde
여기서 A는 bcde로 나누어 떨어지지만 a로 나누면 나머지가 1인수이고
B는 acde로 나누어 떨어지지만 b로 나누면 나머지가 1인 수이고...
E는 abcd로 나누어 떨어지지만 e로 나누면 나머지가 1인수이다.
이말이 도데체 무슨 말일까.
A가 bcde로 나누어 떨어진다는 소리는 A가 bcde의 배수라는 소리이다.
A = bcde의 배수
B = acde의 배수
C = abde의 배수
D = abce의 배수
E = abcd의 배수
mxabcde = abcde의 배수
결국 (Ap + Bq + Cr + Ds + Et + m x abcde) <- 이 수는 a로 나누었을때 나머지가 p , b로 나누었을 때 나머지가 q ,c로 나누었을 때 나머지가 r ...
A,B,C,D,E 모두 각각 a,b,c,d,e,로 나누었을 때 나머지가 1이기에 p,q,r,s,t,배를 하면 나머지가 p,q,r,s,t가 된다.
어떤 수에 배를 한다는 것을 나머지도 배가 된기 때문이다.
즉 7x1을 3으로 나누면 나머지가 1이다.
7x2을 3으로 나누면 나머지가 2이다.
7x3을 3으로 나누면 나머지가 0이다.
7x4을 3으로 나누면 나머지가 다시 1이다.
즉 000 | 0 -> 3하고 나머지 1개
두배하면 000 | 0 -> 나머지도 2배
하지만 3배하면 000 | 0 -> 나누어 떨어지니 0개 . 이건당연히 3배하는 순간 3의 배수가 되기때문에 나누어떨어진다.
당연히 Ap는 a로 나누었을 때 나머지가 1인 수이니 p는 3의 배수가 되면 안되겠지요.
결국 a로 나누었을 때 Bq+Cr+Ds+Et+mxabcde 는 모두 a로 나누어떨어지고
결국 Ap의 A는 a로 나누었을 때 나머지가 1이기에 p를 곱해주면 나머지가 p가 된다.
이 식은 위의 식 70*1 + 21*2 + 15*3 -157과 비슷한데
다시 정리하면 (5*7*2)*1 + (3*7)*2 + (3*5)*3 +(-1)*3*5*7 꼴로 바꿀 수 있고
A*p + B*q + C*r + m x abc
위의 꼴과 같아진다.
(5*7)*2 + (3*7)*1 + (3*5)*1 +(-1)*3*5*7
이 식에서 5*7에 2배를 하여 나머지가 1인수로 만들어 (5*7*2)*1이 되었고
(3*7)*1을 (3*7)*2를 하여 나머지가 2인 수로
(3*5)*1을 (3*5)*3를 하여 나머지가 3인 수로 바꾼것이다.
이 식에서 a,b,c는 3,5,7이며 p,q,r은 1,2,3이다.
조금 더 깔끔한 식을 사용할 필요가 있다.
mod개념이 필요하다.
양의 정수 m에 대하여 , 두 정수 a,b의 차가 m의 배수일 때 , 즉 m|(a-b)일 때,
a와 b는 m에 관하여 합동이라 하고 , 이것을 a≡b (mod m) 으로 나타낸다.
3개로 나누면 1개가 남고 5개로 나누면 2개가 남고 7개로 나누면 3개가 남는 것을
x≡1 (mod 3)
x≡2 (mod 5)
x≡3 (mod 7)
로 간단히 표현할 수가 있다.
1. x는 3*5*7로 나누었을 때 답이 나온다.
즉, 3,5,7의 최소공배수 105로 나누어야 한다.
2. (1*35*2) + (2*21*1) + (3*15*1)
a. (1*35*2) 35는 5*7이므로 5와 7의 mod 연산에서 항상 0이다.
(35*2)는 mod 3 연산에서 나머지가 1이다.
1*(35*2)는 mod 3 연산에서 나머지가 1이다.
b. (2*21*1) 21는 3*7이므로 3와 7의 mod 연산에서 항상 0이다.
(21*1)는 mod 5 연산에서 나머지가 1이다.
2*(21*1)는 mod 5 연산에서 나머지가 2이다.
c. (3*15*1) 15는 3*5이므로 3와 5의 mod 연산에서 항상 0이다.
(15*1)는 mod 7 연산에서 나머지가 1이다.
3*(15*1)는 mod 7 연산에서 나머지가 3이다.
a,b,c 는 mod 105(3*5*7) 연산에서
a를 제외하고는 모두 3의 배수이므로
a mod 3 = a + b + c mod 3과 같다.
b를 제외하고는 모두 5의 배수이므로
b mod 5 = a + b + c mod 5와 같다.
c를 제외하고는 모두 7의 배수이므로
c mod 7 = a + b + c mod 7과 같다.
즉 a + b + c 는 모든 조건을 만족한다.
(3으로 나누면 나머지가 1, 5로 나눈 나머지가 2, 7로 나눈 나머지가 3 인 정수)
3. 위 식의 결과 값은 157 이다.
157 +(m)x105(3*5*7) (m은 정수)
의 모든 값 또한 모든 조건을 만족할 것이다.
52, 157, 262 ... (m=-1, m=0, m=1...)
이는 곧 157 mod 105로 표현할 수 있다.
157이 105보다 크기 때문에 105+52로 표현하고
결국 105는 나눠지고 나머지 52만 남게 된다.
[동아일보]에서 냈던 중국인 나머지 정리와 관련된 문제 예시라네요...
맹랑하기 짝이 없는 한 소녀가 길을 가는 할아버지를 붙잡고 다음과 같은 질문을 한다.
"할아버지 나이를 3으로 나눈 나머지는 얼마입니까? 또 5로 나눈 나머지랑 7로 나눈 나머지를 알려주세요
그럼 제가 할아버지 나이를 알아맞혀 보겠습니다."
할아버지 왈,
"3으로 나눈 나머지는 2이고, 5로 나눈 나머지는 3, 그리고 7로 나눈 나머지는 5인데...
그런데 너는 무슨 수로 내 나이를 알아맞히겠다는 것이냐?"
잠시 땅바닥에 주저앉아서 계산에 몰두하던 맹랑한 소녀 왈,
"할아버지 나이는 68세임에 틀림없어요. 그렇죠?"
당황한 할아버지가 '도데체 무슨 수로 그렇게 순신간에 나이를 알아냈느냐?'고 묻자
맹랑한 소녀가 자신의 계산법을 제시한다.
2x70+3x21+5x15-105x2=68
그래도 할아버지가 납득하지 못하자, 맹랑한 소녀 왈,
"70은 5와 7의 배수이면서 3으로 나눈 나머지가 1인 자연수입니다.
따라서 2x70은 5와 7의 배수이면서 동시에 3으로 나눈 나머지가 2입니다.
21은 3과 7의 배수이면서 동시에 5로 나눈 나머지가 1입니다.
따라서 3x21은 3과 7의 배수이면서 동시에 5로 나눈 나머지가 3입니다.
15는 3과 5의 배수이면서 7로 나눈 나머지가 1인 자연수입니다.
따라서 5x15는 3과 5의 배수이면서 7로 나눈 나머지가 5입니다.
그런데 할아버지 나이는 100세가 넘어 보이지는 않아서 3x5x7=105를 두번 뺐습니다.
할아버지 나이는 68세가 틀림없습니다."
'알고리즘' 카테고리의 다른 글
| 확장된 유클리드 JAVA 소스 (0) | 2014.12.10 |
|---|
