<문제>어떤 노인의 나이를 3,5,7 각각의 수로 나눈 나머지를 안다고 가정하자. 그때 노인의 나이를 구하는 방법은

3으로 나눈 나머지에 70을 곱하고, 5로 나눈 나머지에 21을 곶하며, 7로 나눈 나머지에 15를 곱한다. 그 각각의 결과를 더한 값이 105를 넘지않으면 그값이 노인의 나이고, 105를 넘으면 105로 나눈 나머지가 노인의 나이다.

이거 설명좀해주세요. 도저히 이해못하겠어요.

<풀이>

*두 자연수p, q 가 서로 소이면, q의 배수이면서 p로 나눈 나머지가 1인 자연수가 반드시 존재한다.

(증명)왜냐하면, [eqn: q TIMES 1,`q TIMES 2,``…``,`q TIMES p] 중 어느 두 수([eqn: q TIMES i,``q TIMES j(i LEQ j LEQ p)])가 [eqn: p]로 나눈 나머지가 같다면, [eqn: jq-iq=(j-i)q] 는 [eqn: p]의 배수, 한편 [eqn: p,``q] 가 서로 소이므로 [eqn: (j-i)]가 [eqn: p]의 배수이다.

따라서, [eqn: j-i=0], 즉, [eqn: j=i].

따라서, [eqn: q TIMES 1,`q TIMES 2,``…``,`q TIMES p] 들은 [eqn: p]로 나눈 나머지가 각 각 다르므로 이 수들 중에는 p로 나눈 나머지가 1인 수가 반드시 존재한다.

*3, 5, 7 로 나눈 나머지가 각 각 [eqn: r _{3} ,``r _{5} ,``r _{7}]인 두 수를 [eqn: x,`y] 라 하면, [eqn: (x-y)]는 3, 5, 7의 공배수이므로 [eqn: (x-y)]는 105[eqn: (=3 TIMES 5 TIMES 7)]의 배수, 즉 [eqn: y=105k+x]([eqn: k]는 정수).

즉, 3, 5, 7 로 나눈 나머지가 서로 같은 수들은 105로 나눈 나머지가 서로 같다.

따라서, 70 : (5× 7)의 배수이며 3으로 나눈 나머지가 1인 수, 21 : (3× 7)의 배수이며 5으로 나눈 나머지가 1인 수, 15 : (3× 5)의 배수이며 7 로 나눈 나머지가 1인 수 이므로 어떤 수[eqn: x]를 3, 5, 7 로 나눈 나머지가 각 각 [eqn: r _{3} ,``r _{5} ,``r _{7}]라 하면, [eqn: 70r _{3} +21r _{5} +15r _{7}] 또한 3, 5, 7 로 나눈 나머지가 각 각 [eqn: r _{3} ,``r _{5} ,``r _{7}]인 수 이므로 [eqn: x] 와 [eqn: 70r _{3} +21r _{5} +15r _{7}] 는 105로 나눈 나머지가 서로 같다.

따라서 노인의 나이를 3으로 나눈 나머지에 70을 곱하고, 5로 나눈 나머지에 21을 곱하며, 7로 나눈 나머지에 15를 곱한다. 그 각각의 결과를 더한 값이 105를 넘지 않으면 그 값이 노인의 나이고, 105를 넘으면 105로 나눈 나머지가 노인의 나이가 된다.

같은 방법으로

21(3× 7)이하의 어떤 수에 대하여 3으로 나눈 나머지에 7를 곱하고, 7 로 나눈 나머지에 15을 곱하여 그 각 각의 결과를 더한 값이 21을 넘지 않으면 그 값이 그 수가 되고 그 값이 21을 넘으면 21 로 나눈 나머지가 그 수가 된다.

같은 방법으로

30(2× 3× 5)이하의 어떤 수에 대하여 2로 나눈 나머지에 15를 곱하고, 3으로 나눈 나머지에 10을 곱하며, 5로 나눈 나머지에 6을 곱하여 그 각 각의 결과를 더한 값이 30을 넘지 않으면 그 값이 그 수가 되고 그 값이 30을 넘으면 30으로 나눈 나머지가 그 수가 된다.- 끝 -