조화수(Harmonic Number)는 자연수가 될 수 없음을 증명하기

조화수란 무엇인가?

조화수가 대체 무엇일까요?

임의의 양의 정수 n에 대하여 n번째 Harmonic Number Hn은 다음과 같이 정의됩니다.

 

Hn = 1+1/2+1/3+...+1/n으로 정의되는 수를 n번째 조화수 라고 합니다.

 

오늘은 임의의 자연수 n에 대하여 Hn은 절대 자연수가 될 수 없음을 증명하도록 하겠습니다.

 

조화수는 자연수가 될 수 없음

일단 자연수 M을 다음과 같이 정의해 봅시다.

M = lcm(1,2,3,4,...,n)

(M은 1부터 n까지의 모든 정수에 대한 최소공배수)

 

 

그러면 1부터 n까지의 모든 정수 k에 대하여

k * ak = M을 만족시키는 정수 ak가 반드시 존재합니다.

 

그러면 Hn을 다음과 같은 식으로 바꿀 수가 있습니다.

 

여기서 M은 반드시 짝수입니다.

왜 그럴까요?

 

 

아까 M은 1,2,3,...,n의 최소공배수라고 하였습니다.

n>=2이므로

반드시 M은 2라는 소인수를 포함하여야만 합니다.

그러므로 M은 짝수가 되고 싶지 않아도 반드시 짝수가 됩니다.

 

그리고..

먼저 다음과 같은 사실을 받아들이도록 합시다.

위 식은 n >= 2일 때

하늘이 무너져도 반드시 홀수가 되는 수 입니다.

 

그러므로 Hn = (홀수 / 짝수)가 되어버립니다.

홀수를 짝수로 나눈 꼴이니,

이 Hn이라는 조화수는 절대 자연수가 될 수 없는 것입니다.

 

여기서 

이게 왜 반드시 홀수인지를 증명해 보도록 합시다.

 

이 증명을 이해할 때 약간의 논리적 비약과 수학적인 트릭이 있다면 쉽게 할 수 있습니다.

 

일단 모든 자연수 n에 대하여

 

2^q <= n < 2^(q+1)을 만족하는 정수 q가 반드시 존재합니다.

 

 

1부터 n까지의 자연수

1,2,3,...,n에서

2^q <= n < 2^(q+1)을 만족하는 정수 q가 있다고 해 봅시다.

 

그러면 다음과 같이 수를 쭉 나열할 수가 있습니다.

 

 

목적을 다시 상기시켜보도록 하겠습니다.

우리가 증명하고자 하는 것은

a1 + a2 + a3 + ... + ak가 왜 반드시 홀수인가?입니다.

 

 

여기서 M은 아까 말씀드린 바와 같이

1,2,3,...,n의 최소공배수 입니다.

그리고 1<= k <= n인 k에 대하여

k * ak = M 을 만족시키는 정수 ak가 존재한다고 하였습니다.

 

2^q <= n < 2^(q+1)을 만족하므로 

최소공배수 M은 다음과 같이 나타낼 수가 있습니다

M = (2^q * 어떤 홀수)

 

k = 2^q라고 해 봅시다

k * ak = M에서

k = 2^q이므로 당연히 ak는 홀수입니다.

 

그리고 k != 2^q일 때,

k * ak = M = 2^q * (홀수) 형태가 되어야 합니다.

 

그런데 n이하의 정수 중에 2 ^ q라는 인자를 가지고 있는 정수는

2^q밖에 없습니다.

 

 

그러므로 

k * ak = M에서

k * ak = 2 ^ q * (어떤 홀수)

k는 2^q라는 약수를 가지고 있지 않으므로

k * ak 전체가 2^q라는 약수를 포함하게 만들기 위해서는

ak에 반드시 2라는 소인수가 있어야 합니다.

 

 

이게 이 증명의 핵심입니다.

이것만 이해하면 되는데

직관적으로 이해하기가 어려우므로 계속 시뮬레이션을 돌려 보도록 해 주십시오.

 

그러므로 ak는 2라는 소인수를 포함하므로 반드시 짝수입니다.

 

그러면 다음과 같은 형태가 되죠

 

그러면 a1 + a2 + a3 + .. + an의 결과를 확인해 볼까요?

a1,a2,a3...an중 한 개가 홀수이고 나머지는 전부 짝수입니다.

그러면 이걸 다 더했을 때는 반드시 홀수가 나오게 됩니다.

 

 

그러므로 다음 식은 홀수라는 것이 증명되었습니다.

 

증명 끝났습니다

 

여기서 M이 짝수이기 때문에 

전체 Hn은 홀수 / 짝수의 형태가 되 버리고

따라서 Hn은 절대로 자연수가 될 수 없는 것입니다.

 

 

이상 조화수가 자연수가 될 수 없다는 사실을 증명하였습니다.

감사합니다.