영남학당(嶺南學堂)

ㆍ작성자	진석호
ㆍ작성일	개국619(2010)년 2월 18일 (목) 20:31 [술시(戌時):초경(初更)]
ㆍ문서분류	학사

ㆍ추천: 0 ㆍ열람: 653

[훈장] 문제(자연수의 한가지 성질)에 대한 답입니다

문제:

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

답: 답이 예상치 않게 길어졌지만 꾹 참고 읽어주십시오. 걸리는 부분이 있다면 아무것이나 질문해도 좋습니다.

문제에 대한 답입니다. 이해를 돕기 위해 일단 경험적으로 패턴을 파악한 후, 증명을 하기로 하겠습니다.

[경험, 패턴파악] 예를 들어 n이 10일 때를 살펴 봅시다.

n=10일 때 약수는 1,2,5,10 이렇게 4개가 있습니다. 그리고 a(1)=1, a(2)=1, a(5)=4, a(10)=4가 됩니다. 1+1+4+4=10으로 n과 같네요. 제가 말한 답 또한 n이었습니다. 그렇다면 어떤 패턴이 있을 것입니다.

생각해 봅시다. a(10)=10과 서로소이면서 1이상인 자연수들의 갯수였습니다. 1,3,7,9였네요. 마찬가지로 a(5)는 5와 서로소이면서 1이상인 자연수들의 갯수입니다. 여기에 해당하는 1부터 10까지의 수들은 어떤 것들이 될까요? 즉 제가 할려고 하는 것은 저 각각의 a(d)들에 a(d)개의 자연수들을 할당해줘서 1부터 n까지의 수들에 대응하는 함수를 만들고 싶은 것입니다. 위에서처럼 a(10)=4에 1,3,7,9와 같은 네개의 자연수를 할당해 준 것처럼 말이죠.

앞에서 1,3,7,9는 소비했으니 나머지 6개 중에 4개를 잘 선택해줘야 합니다. 성질을 잘 유지하면서요. 5와 서로소인 자연수는 1,2,3,4 이렇게 있는데 10은 5의 두배이니 2,4,6,8 이렇게 선택해 주고 싶습니다. 일단 1,3,7,9는 건드리지 않았네요.

비슷하게 합시다. a(2)=1이므로 1*5=5를 할당해 주고, a(1)=1이므로 1*10=10을 할당해 줍니다.

그리고 봅시다. 1,2,3,4,5,6,7,8,9,10 모두 커버됐습니다. 일단은 됐네요. 그다음엔 규칙이 있는지 생각해 봐야겠죠. 우연히 된 것일 수도 있으니까요. 하지만 이것은 알고리즘이 있는 것 같으니 일단 될 것 같다고 생각이 듭니다. 따라서 패턴을 찾게 됩니다. 어떤 패턴이 있을까요?

a(10)에 대응하는 수들을 살펴봅시다. 1,3,7,9. 말그대로 10과 서로소인 수들입니다.
a(5)에 대응하는 수들을 살펴봅시다. 2,4,6,8. 2의 배수들이네요. 그리고 5와는 서로소입니다.
a(2)에 대응하는 수들을 살펴봅시다. 5. 5의 배수네요. 2와는 서로소입니다.
a(1)에 대응하는 수들을 살펴봅시다. 10. 10의 배수네요. 1과는 서로소입니다.

무엇이 보이나요? 1부터 10까지의 자연수가 네개 중 하나에 속한다는 것이 보이나요?

다시 말해서 10=2*5이니, 1부터 10까지의 자연수를 아무거나 택해도 2,5의 배수이거나, 5의 배수이고 2의 배수는 아니거나, 2의 배수이고 5의 배수는 아니거나, 2의 배수도 아니고 5의 배수도 아니거나 중의 하나라는 얘기입니다. 이런 말을 일반적인 n에 대해서도 얘기할 수 있을까요? 당연합니다. 약수들의 배수이냐 아니냐를 나눠놓은 것에 불과하기 때문이죠.

다음은 위의 경험을 바탕으로 한 문제에 대한 증명입니다.

[증명] 첫번째 (1)의 사실이 핵심적입니다.

(1)

사실: n의 약수 d 의 배수이면서 그것보다 큰 약수로 나눠지지 않는, n이하의 자연수의 갯수

(예를 들어 n=30이고 d를 5라고 하면 5의 배수만 되고 10이나 15,30 의 배수는 되지 않는 수들입니다. 즉 5,10,15,20,25,30 중에서 5,25 이렇게 두개만 되네요.)

는 a(n/d), 즉 n/d와 서로소인 n/d 이하의 자연수의 갯수이다.

(예) n=30, d=5라고 하면, 5의 배수이면서 그것보다 큰 약수로 안나눠지는 것은 위에서 보듯이 6,30 이렇게 2개입니다. 그리고 n/d=6과 서로소인 6이하의 자연수는 1과 5로 역시 두개입니다.

"사실"의 증명:

위의 조건을 만족하는 n이하의 자연수를 m이라고 해봅시다. m은 d의 배수밖에 될 수 없으므로 d로 나누면 n/d와는 서로소가 되어야 합니다. 왜냐하면 더 공약수가 있다고 하면 m을 d로 나눠지고 또 그 수로 나눠져서 d보다 큰 n의 약수로 나눠질 수 없다는 가정에 위배되기 때문입니다. 예를 들어 n=36, d=6일 때, 위의 조건을 만족하는 수는 6,12,18,24,30,36 중에 6,30 두개뿐이네요. 6과 30을 6으로 나누면 1,5이고 36/6=6과 서로소가 됩니다.

반대로, n/d와 서로소인 n/d이하의 자연수들을 생각해 봅시다. 이번엔 반대로 각 수에 d를 곱합시다. 그러면, 각 수들은 d를 곱했으니 당연히 d의 배수가 되겠죠? 그리고 d보다 큰 어떤 약수로도 나눠지지 않는다는 것을 알 수 있습니다. 당연하죠. n=d*(n/d)인데 d보다 큰 약수의 배수가 되려면 n/d의 약수로 더 나눠져야 하는데, 가정상 n/d와 서로소인 자연수를 골랐으니 그럴 수 밖에 없게 됩니다. 아까의 예를 계속 이용한다면, n=36일 때 d=6이라고 했으면 n/d=6과 서로소인 수는 1,5 이고, d=6을 곱하면 6,30이 되어 아까와 반대로 6과 30을 얻게 됩니다.

지금까지 한 것이 뭔가요? 두 집합 A={n의 약수 d 의 배수이면서 그것보다 큰 약수로 나눠지지 않는, n이하의 자연수}와 B={n/d와 서로소인 n/d 이하의 자연수} 사이에 일대일 대응이 있다, 다시 말해 두 집합의 원소갯수는 같다는 것을 증명한 것입니다. 정보를 하나도 잃지 않았다는 거지요. 따라서 "주장"에 대한 증명이 되었습니다. 증명끝.

(2) 증명을 완료하겠습니다.

실상, (1)의 사실에 의해서 증명은 거의 끝났습니다.

우선, d가 n의 약수이면 n/d 또한 n의 약수이므로, a(n/d)들의 합은 a(d)들의 합과 같다는 것을 주의해 주십시오.

그리고, n이하의 자연수를 골랐을 때, n과의 최대공약수가 n의 약수중 그 수를 나누는 최대 자연수라는 것을 유념한다면,

"n의 약수 d 의 배수이면서 그것보다 큰 약수로 나눠지지 않는, n이하의 자연수의 갯수"들을 모든 n의 약수 d에 대해서 더한 합이, 다름아닌 n이라는 것을 알 수가 있게 됩니다.

그런데 (1)의 사실에 의해, a(n/d) = n의 약수 d 의 배수이면서 그것보다 큰 약수로 나눠지지 않는, n이하의 자연수의 갯수였으므로,

결론적으로 "n= a(d)들의 합"이라는 사실이 증명되었습니다.

막상 적고 보니 많이 어려워 보이는군요;; 하지만 차분히 생각하면서 읽는다면 충분히 이해하실 수 있을거라 생각합니다. 사실 이 사실은 대수학의 한 영역인 군론을 조금 배운다면 쉽게 증명할 수 있는 사실이지만 여기서는 바로 증명하려고 하니 쓸게 많이 필요하네요. 다음 기회에 대수학의 군론에 대해서 논하도록 하지요.

여기까지 꾹 참고 읽어주신 분께는 상금으로 10냥을 드리겠습니다. 부디 읽어주신 분만 양심적으로 댓글을 달아주십시오^^;;(저 거지임;)

감사합니다.

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

김재열

619('10)-02-18 22:25

이건 하나의 훌륭한 강의가 되었네요. 정말 푸는 방법을 시작부터 끝까지 알려 주심에 감사드립니다.
수학문제풀이 글인데 참 재미가 있네요.^^


진석호	계속 관심가져 주세요. 감사합니다.^^	02/20 22:37

진석호	약속드린대로 장학금을 드리겠습니다. 장터에 글을 올렸으니 수령해 주세요 . ^^	02/21 17:44

이수현

619('10)-02-20 17:33

소예님 오랜 만에 강의 듣고 갑니다. 허허허
그런데 너무 오랫동안 쉬었던 것 같습니다. ^^;;

그래도 수학에 흥미가 느껴집니다. 재밌구요. 시간이 날 때 모든 강의 내용을 정독해서 보도록 하겠습니다. ^^


진석호	감사합니다.^^	02/20 22:37

진석호	마찬가지로 장터에 글을 올렸으니 수령해 주세요 . ^^	02/21 17:44

김동현

619('10)-04-07 14:28

서로수라는 것에 대해서 잘 알게 되었습니다.

이것은 문제 풀이 글인데도 불구하고 진석호님이 강의를 잘 진행하셔서 그런지 재미있는 것 같습니다. ^^


진석호	재미를 느끼셨다니 저도 정말 좋네요. 약속대로 장터에 10냥을 올리겠습니다. ^^	04/09 13:19

김동현	상금이 있었군요... 수학에 관심이 있어서 들었는데.. 감사합니다.	04/09 14:35