영남학당(嶺南學堂)

ㆍ작성자	진석호
ㆍ작성일	개국619(2010)년 2월 8일 (월) 14:10 [미시(未時)]
ㆍ문서분류	학사

ㆍ추천: 0 ㆍ열람: 351

[훈장] 문제 (자연수의 한가지 성질)

이제부터 문제는, 문제 하나만 올리는 경우에는 학사란에 올리도록 하겠습니다.

자, 오늘은 자연수에 대한 어떤 성질을 알아보려고 합니다. 일단 문제부터 제시하겠습니다.

자연수 n을 고릅니다. 1부터 n까지의 자연수중, n과 서로소인 것(즉 최대공약수가 1인 것이죠?)들의 갯수를 a(n)이라고 합시다. 예를 들어 n=10을 골랐을 때, 10과 서로소인 자연수는 1,3,7,9 이렇게 4개이므로 a(10)=4가 됩니다.

이때, "n의 약수 d에 대해 a(d)들을 구해서 다 더하면 뭐가 될까요?"가 문제입니다.

문제의 이해를 돕기 위해 예를 들어 보겠습니다. n=15라고 해볼까요? 약수는 1,3,5,15입니다.

그러면 a(1)=1, a(3)=2, a(5)=4, a(15)=8이 됩니다. (예를 들어 15와 서로소인 자연수는 1,2,4,7,8,11,13,14 이렇게 8개가 됩니다.) 이것들을 다 더하면 1+2+4+8=15가 되네요.

답을 예상하기는 실험을 좀 해보면 쉽습니다. 답을 예상하고 그것이 왜 그런지를 생각해 보고 알아내는 것이 이번 문제의 취지중 하나입니다. ^^

http://www.1392.org/bbs?laed31:325

진석호 619('10)-02-08 21:56	유효 댓글은 다음주까지 받겠습니다.

진석호 619('10)-02-09 11:09	답이 뭘까요? 일단 답을 제시하는 선착순 한 분께 약소하지만 10냥을 상금으로 드리겠습니다.

진석호 619('10)-02-11 13:56	힌트입니다. a(d) (d는 n의 약수)들의 의미를 다시 한번 생각해 보세요.

진석호 619('10)-02-15 15:05	답을 알아내신 분이 없군요. 우선 답을 제시하고 사흘 후에 풀이를 발표하겠습니다. 답은 n입니다.

김재열 619('10)-02-16 16:13	자연수의 성질이 참 특이합니다. 신기하면서도, 안 풀리니 머리가 아프네요. 힌트를 받아도 도저히 생각의 진도가 나가지 않습니다. 차분하게 풀이를 기다려야겠네요. 悲.

서양갑 619('10)-02-17 14:05	만약 n이 소수라면 a(n)= n-1 이 됩니다. 만약 n이 소수가 아니라면 a(n)=(n-1) - {a(e_1) + ... + a(e_k)}, 여기서 e_1, ... , e_k 는 1과 자기 자신을 제외한 n의 약수들 입니다. 즉, n의 약수 d에 대해 a(d)들을 구해서 다 더하면, a(1)+a(e_1) + ... + a(e_k)+a(n) = 1 + {a(e_1) + ... + a(e_k)} + (n - 1) - {a(e_1) + ... + a(e_k)} = 1 + n -1 = n 이 됨을 보일 수 있습니다. e.g) n=12 라면 약수는 1, 2, 3, 4, 6, 12 가 됩니다. a(1)=1 이고, 2와 3은 소수이므로, a(2)=1, a(3)=2, 이고, a(4)=3-a(2)=2, a(6)=5-a(2)-a(3)=2, a(12)=11-a(2)-a(3)-a(4)-a(6)=4 a(1) + ... + a(12) = 12

진석호 619('10)-02-17 16:56	답하신 부분 중에 "만약 n이 소수가 아니라면 a(n)=(n-1) - {a(e_1) + ... + a(e_k)}, 여기서 e_1, ... , e_k 는 1과 자기 자신을 제외한 n의 약수들 입니다." 가 왜 성립하는지를 설명해 주셔야 합니다. 위의 말은 증명하고자 하는 것과 거의 같은 말을 되풀이한 것이거든요. 이것이 왜 그렇게 되는지 이유를 묻는 것입니다. 조금만 더 생각하시면 이유를 찾으실 수 있을거라 생각합니다. ^^; ps. 소수일 경우에는 물론 맞습니다^^

진석호 619('10)-02-18 21:08	답은 따로 글로 올렸습니다.