Perfect Number

이 page는 앞으로 많이 보태질 계획입니다. 누구나 글을 쓸 수 있습니다. 정성을 모아주십시오. ( 수학식 쓰기)

완전수

자연수 세계에는 신비로운 질서가 있다. 땅 위와 땅아래 강이 흐르고 바다가 있고 샘이 흐르고 풀이 나고 동물들이 저마다 자기만의 법칙으로 살아가듯 자연수들도 혹은 이렇게 혹은 저렇게 묶이고 풀리면서 특별한 성질과 질서를 보여주곤 한다. 어떤 것은 그 모습을 쉽게 드러내고 어떤 것들은 유혹은 빠르고 강력하지만, 쉽게 자기를 드러내지 않는다. 아주 야릇하거나 괴상해서 들여다볼수록 신기한 데 좀처럼 그 성질을 파악하기 힘든 수들 중 이참에는 '완전수'라는 '특별한' 이름을 가진 수들을 함께 보도록 하자.

완전수는 고대 그리스의 문헌에서 종종 등장한다. 플라톤의 저작들(예:리퍼블릭(republic))에서도 벗수(amicable numbers)와 함께 신비로움으로 채색한 채 나타나고 유클리드 원론 9 권의 마지막 부분에 더 수학적인 모양으로 나타나 지금까지 전해진다. 이 주제 직전에는 소수의 무제한성을 다루었다. 알려졌다시피 완전수란 그 수를 나누는 수들의 합이 그 수가 되는 수다. 물론, 이때 그 자신의 수는 제외된다. 다시말하면 그 수를 곱셈하여 그 수를 만드는데 참여한 수들을 더하면 그 수가 되는 경우다. 곱셈에 참여하는 수들을 약수라고 부르니, 간단히 정의하면 아래와 같다.

정의 (완전수) : 어떤 자연수 N 의 약수들을 '덧셈'하면 그 수가 될 때, 이 수 N 을 완전수라 한다.

어떤 자연수 N 을 곱셈으로 구성할 수 있는 수들을 덧셈 연산으로도 구성할 수 있다면, 이런 특별한 수들이 '완전수'가 되는 셈이다. 완전수는 어떤 수를 이루는 '덧셈 요인'과 '곱셈 요인'의 관계가 뚜렷하게, 완전하게, 드러나 있는 수들이다. 일반적으로 자연수에 대해서는 덧셈과 곱셈의 관계는 뚜렷하지 않다는 점을 생각해보면, 완전수의 이런 특별한 성질이 수를 사랑한 사람들을 유혹하지 않았을리 없다.

완전수는 고대 그리스에서 이미 네 개 발견되었다. 6, 28, 496, 8128 이었다. 그렇다면 '질서'를 만들어보자면, 당장 이런 호기심이 들 수 있다. 예를들면,

• 완전수는 항상 6 과 8 만 나오지 않을까? 어디, 이보다 더 강한 가설을 세워보자, 완전수는 6으로 끝나고 그 다음은 8로 끝나면서 6과 8의 반복으로 끝나는 것은 아닐까?
• 처음 완전수는 한자리, 두번째는 두자리, 세번째는 세자리 ... 처럼 가니 어쩌면 다섯번째는 다섯자리에서 발견되지 않을까?

너무 만만하게 생각하고 덤벼들었다. 역시, 그런 추측들은 아니오! 로 답하게 된다. 어떤 수에 대해 덧셈과 곱셈으로 구성하는 원소들이 같다니, 그런 신비로운 성질을 가진 수들이 그렇게 단순한 성질을 가졌다면 그것이 되려 놀라왔을 것이다.

완전수를 생각하며

자연수의 열에서 작은 수부터, 차례차례 찾아갈 수 있는데 고대 그리스에 알려진 완전수는 앞에서 말했듯이 네 수였다. 6, 28, 496, 8128 이 수들을 더 깊이 '분석'해보자.

구체적인 것에서 일반 법칙찾아가기 : 귀납적 방법(Induction)

6, 28, 496, 8128 네 수가 알려졌다 해보자. 그리고 그것으로부터 일반적 법칙을 찾아간다고 해보자.

$6=2\cdot 3=2(2^{2}-1)=2(2+1)(2-1)=2^{2}+1=4+2$

$28=2^{2}7=2^{2}(2^{3}-1)=2^{2}(2^{2}+2+1)=2^{4}+2^{3}=2^{2}=16+8+4$

$496=2^{4}31=2^{4}(2^{5}-1)=2^{4}(2^{4}+2^{3}+2^{2}+2+1)=2^{8}+2^{7}+2^{6}+2^{5}+2^{4}=256+128+64+32+16$

$8128=2^{6}127=2^{6}(2^{7}-1)=2^{6}(2^{6}+2^{5}+2^{4}+2^{3}+2^{2}+2+1)=2^{12}+2^{11}+2^{10}+2^{9}+2^{8}+2^{7}+2^{6}=4096+2048+1024+512+256+128$

이 정도로 쪼개어 생각해보니 이 네 수의 구조가 서서히 드러나고 있다. 가장 먼저 눈에 띄는 것은 무엇인가?

모두 $2^{n}(2^{n+1}-1)$ 꼴이다.

그렇다면 n 이 위의 경우가 아닌 3, 5 의 경우는 어떻게 될까 ?

$2^{3}15=2^{3}(2^{4}-1)=2^{3}(2^{3}+2^{2}+2+1)=2^{6}+2^{5}+2^{4}+2^{3}=64+32+16+8=120$

$2^{5}63=2^{5}(2^{6}-1)=2^{5}(2^{5}+2^{4}+2^{3}+2^{2}+2+1)=2^{10}+2^{9}+2^{8}+2^{7}+2^{6}+2^{5}=2016$

스스로 검토해보라. 확인할 수 있듯, 이 수들은 완전수가 아니다. 그렇다면 앞의 경우와 이것은 어떤 차이가 있나? 가설을 세워보자.

다음 조건 중 어떤 것이 만족할 때, $2^{n}(2^{n+1}-1)$ 은 완전수다. 물론 이 수는 짝수다.

1. n 이 짝수다. (n 이 1 인 경우는 빼고 생각한다고 하자.)
2. n+1 이 소수다.
3. $2^{n}-1$ 이 소수다.

위의 세 문장은 어떤 관계일까?

$3\ \Rightarrow \ 2\ \Rightarrow \ 1$

일까? 물론 그렇지 않다. 첫번째 조건은 너무 단순하다. 두번째, 세번째 경우는 잠시 두고 보도록 하자.

일반적인 방법(deduction)

그리 크지 않은 자연수 중에서 완전수를 찾아가기는 알고리듬은? 모든 완전수는 아니더라도. 우선 전체 열에서 완전수일 수 없는 것들에 대해 생각해보자. 다음의 법칙들을 스스로 증명해볼 수 있다.

• p 가 소수면 p 은 완전수가 아니다. ($\forall p\ (p\in Pr\ \rightarrow \ p\notin Pf)$)
• p 가 소수면 p 의 n-제곱은 완전수가 아니다. ($\forall p\forall n\ (p\in Pr\ \rightarrow \ p^{n}\notin Pf)$)

자. 그렇다면 이제 소수와 소수 하나의 제곱으로 이루어지지 않은 합성수를 보자. 간단한 경우로, 두 소수만 참여했고 간단한 경우부터 보고 점점 일반화 시켜 가보자.

어떤 수 N 이 $pq^{m}$ 이라고 가정해보자.

그렇다면 N 은, 1과 그 자신을 포함해서, 아래의 수들로 나누어 떨어질 것이다.

$1,\ p,\ q,\ pq,\ q^{2},\ pq^{2},\ q^{3},\ pq^{3},\ \dots ,q^{m},\ pq^{m}$

산술의 기본정리 에 따라 이 약수들 말고 다른 약수들은 있을 수 없다. 이것들의 합을 들여다보면

$1+p+q+pq+q^{2}+pq^{2}+q^{3}+pq^{3}+\cdots +q^{m}+pq^{m}=(1+p)(1+q+q^{2}+q^{3}+\cdots +q^{m})$

이고 이를 간단히 표현하면

$(1+p)({\frac {q^{m+1}-1}{q-1}})$

이다. 앞의 완전수의 예들에서 모두 q 가 2인 경우였다. 더 일반화하기 전에 그런 경우만 먼저 보도록하자. 그런 특수한 수들만 보면,

$(1+p)(2^{m+1}-1)$

다. 이 수 N 가 완전수이기 위해서는 이 약수의 합이 2N 과 같아야 한다. (앞의 약수들의 합은 그 자신 N 을 포함하고 있었다.) 따라서

$(1+p)(2^{m+1}-1)=2\cdot p\cdot (2^{m})=p\cdot 2^{m+1}$

따라서, N 이 완전수이기 위한 필요조건은

$p=2^{m+1}-1$

이다. 따라서 앞에서 추측한대로

$2^{m+1}-1$ 이 소수면 $(2^{m+1}-1)(2^{m})$

은 완전수다. 단, 이 경우는 모든 완전수를 포괄할 수 없을 뿐아니라, 언뜻 보면 매우 특수한 경우의 완전수만 본 것이다. q 가 2 가 아니라면? (다시 말해 짝수가 아니라면?) 그리고 p 도 한번이 아니고 여러번 곱해진 합성수라면? 보다 일반적으로 N 이

$p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{r}^{n_{r}}$

인 경우는 어떻게 될까?

어쨌든 약수들의 합은

$(1+p_{1}+p_{1}^{2}+\cdots +p_{1}^{n_{1}})\cdot (1+p_{2}+p_{2}^{2}+\cdots +p_{2}^{n_{2}})\cdots (1+p_{r}+p_{r}^{2}+\cdots +p_{r}^{n_{r}})$

이고 따라서

$\left({\frac {p_{1}^{n_{1}+1}-1}{p_{1}-1}}\right)\left({\frac {p_{2}^{n_{2}+1}-1}{p_{2}-1}}\right)\cdots \left({\frac {p_{r}^{n_{r}+1}-1}{p_{r}-1}}\right)$

완전수에 대한 유클리드의 정리

$2^{n}-1$은 소수라면 $2^{n-1}(2^{n}-1)$ 는 짝수인 완전수다.

따라서 $2^{n}-1$ 이 소수인 수를 알아내고 그 수로 위의 꼴인 수를 만들어내면 그것은 완전수인데, 다섯번째 완전수

$2^{12}\cdot (2^{13}-1)=33,550,336$

는 이었는데 이 수도 완전수다. (n 이 11일 때는 완전수가 아니다. ) 이 수는 최초 네 개의 완전수가 유클리드 시대에 이미 알려지고서 약 2천년이 지나서야 알려졌다. 왜 그리 오래걸렸을까? 그것은 $2^{13}-1$ 라는 엄청 큰 수가 소수인가 아닌가를 밝힐만한 소수 판정 알고리듬을 모르고 있었기 때문이다. 대체로 그때까지 알려진 가장 유명한 방법은 소위 '에라토스테네스의 체'라는 것인데, 이 방법은 수가 작을수록 효율적이지만 수가 커질수록 매우 비효율적인 방법이다. 근현대로 들어서면서 큰 수에 대해서도 소수를 판별할 알고리듬들이 발견되면서 소수를 기계에 넣어서 판별하는 방법을 시도해갔다. 20세기 초, 4,50년대, 로빈슨-루카스 법이라는 방법을 적용하여 프로그래밍한 다음, 천공기에 뚫어 수를 입력하면 그 결과가 나오는데, 나머지가 없으면 소수고 그럴 경우 0이 계속 이어지는 판정법이다. 하지만 그당시 컴퓨터 용량이 무척 제한적이어서 $2^{257}-1$ 이 소수인가 아닌가를 판별하는데 무려 20년, 700 시간동안 들였다고 한다. 현대 컴퓨터로는 1초도 걸리지 않는다. 이 수는 소수라고 봤던 메르센은 가설(Mersenne conjectures) 은 수정되어야 했다. 왜냐하면 0 들의 행진이 나타나지 않았다. 그런데 $2^{521}-1$ 이나 $2^{607}-1$ 같은 수들은 0 들이 행진을 계속하여 소수로 밝혀졌다. 현재까지 알려진 가장 큰 메르센 소수는$2^{32,582,657}-1$ 이며 현재까지 44개 발견되었다.

완전수에 대한 오일러의 정리

그로부터 약 2 천년이 지나, 오일러는 그 역이라 할만한 조건을 증명해냈다.

짝수인 완전수는 항상 $2^{n-1}(2^{n}-1)$ 꼴 일 수밖에 없다는 것을 보였다.

앞의 두 결과를 종합해보라 어떤 결과가 나오는가?

아울러, $2^{n-1}(2^{n}-1)$ 수는 연속하는 두 수의 곱을 2로 나눈 것이므로 결국 삼각수다.

고 여기까지의 '경험'을 바탕으로 추정해보면,

N 이 완전수라는 사실과 $N=2^{n-1}(2^{n}-1)$ 인 어떤 n 이 있다. 라는 사실은 서로 아주 밀접한 연관관계가 있다는 것을 알 수 있다. 그런데, 모든 자연수 n 에 대해 $N=2^{n-1}(2^{n}-1)$ 이 완전수를 만드는 것은 아니라는 것이 확실하다. 예를들어 n 이 1, 4, 6 같은 경우다. 그렇다면 자연수중 어떤 수들이 그것이 가능할까? 앞의 예에서 가설을 세워볼 수 있는 것이 $2^{n}-1$ 가 소수일 때다. 물론 아무 자연수 n 을 잡는다고해서 그 수가 소수가 될리는 없다. 'n 이 소수면, 그 수가 소수일까?' 그렇지도 않다. 예를들어 n 이 11인 경우를 보자. $2^{11}-1=2047$ 이고 이 수는 23과 89의 곱으로 쪼개진다. 그렇다면 도대체 n 이 어떨 때, $2^{n}-1$ 이 소수가 될까? 이와 관련한 문제를 메르센 가설(merssene conjucture)이라 한다.

또는 $2^{n}-1$ 가 소수 n 이 소수이기만 하면 항상 될까? (다시 말해 모든 소수에 대해서 될까?) 따라서 우리는 위의 사실이 논리적으로 등가인지 아닌지 보기 위해서는 다음의 몇가지 질문에 답을 해야만 한다.

N 이 완전수면 항상 $2^{n-1}(2^{n}-1)$ 인 어떤 n 을 찾을 수 있을까? 그것이 가능하다면 그때의 n 은 어떤 n 들일까?

n 들이 어떨 때, $2^{n-1}(2^{n}-1)=N$ 에서 N 이 완전수가 될까?

하지만 이 질문도 그리 만족스럽지 못하다. 앞에서 이야기했듯이 완전수는 덧셈과 곱셈이 신비롭게도 아주 끈끈하게 연결된 수라 그만큼 그 비밀을 밝혀내기 어려웠을 것이다. 다행히, 여기에 대해 이미 유클리드가 첫발을 내디뎠다. 유클리드 원론 에는 다음의 사실에 대한 증명이 있다.

$2^{n}-1$ 이 소수면, N 은 짝수인 완전수다.

이미 중요한 첫발을 내디딘 셈이다. 그랬기 때문에 새로운 문제들이 줄줄이 이어 나올 수 밖에 없었다.

첫번째 생각할 수 있는 것이 그 정리의 역이다. N 이 짝수인 완전수면 $2^{n-1}(2^{n}-1)=N$ 이게 하는 하는 n 은 $2^{n}-1$ 이도록 하는 n 에 대해

홀수인 완전수에 대해서는? 다시말해 어떤 조건일 때, 홀수인 완전수를 만들어 낼 수 있을까? 아니, 홀수인 완전수가 있기나 한 것일까?

Others

정리 (유클리드)  : $2^{n}-1$ 이 소수면 $2^{n-1}(2^{n}-1)$ 은 짝수인 완전수다.

정리  : 6 을 제외한 짝수인 완전수는 1 부터 $2^{\frac {n-1}{2}}$ 개의 홀수 세제곱의 합으로 나타낼 수 있다.

정리 :$2^{n-1}(2^{n}-1)$ 꼴의 수는 삼각수다.

정리 : 삼각수는 어떤 세제곱수들만의 합으로 나타낼 수 있다.

다음 예를보라.

$6=2^{1}(2^{2}-1)=1+2+3,\,$

$28=2^{2}(2^{3}-1)=1+2+3+4+5+6+7=1^{3}+3^{3},\,$

$496=2^{4}(2^{5}-1)=1+2+3+\cdots +29+30+31=1^{3}+3^{3}+5^{3}+7^{3},\,$

$8128=2^{6}(2^{7}-1)=1+2+3+\cdots +125+126+127=1^{3}+3^{3}+5^{3}+7^{3}+9^{3}+11^{3}+13^{3}+15^{3}.\,$

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia