완전수
1. 수학에서 완전수
1.1. 개요
'''完全數'''
''Perfect number''
완전수란, 자기 자신을 제외한 약수(진약수)들의 합이 자기 자신이 되는 수를 말한다. 예를 들어, 6의 약수는 자기 자신인 6을 제외한 1, 2, 3이고 진약수들의 합은 1 + 2 + 3 = 6, 즉 자기 자신이므로 6은 완전수이다.
수학적으로 표현하자면, 다음 식을 만족시키는 자연수 $$n$$을 완전수라고 한다. 여기서 $$\sigma_1(n)$$은 약수 함수(divisor function)이다.
$$\sigma_1(n)=2n$$
현재까지 알려진 짝수 완전수들은 $$2^{n-1}(2^n-1) $$의 형태로 존재하며, $$2^n-1$$이 소수인 경우에 완전수가 된다.[1][2] 이 때, 이 소수인 $$2^n-1$$을 메르센 소수라 한다. 레온하르트 오일러는 모든 짝수 완전수가 위의 형태임을 증명했으며, 따라서 메르센 소수와 짝수 완전수는 일대일 대응이다.[2]
메르센 소수의 수가 유한한지 무한한지는 알려져 있지 않으므로 짝수 완전수의 유,무한 여부도 알려져 있지 않다. 또한 홀수 완전수가 존재하는지 존재하지 않는지도 알려져 있지 않다. 그러나 만약 홀수 완전수가 존재한다면, 그 수는 최소한 101500 이상인 것으로 알려져 있다.
관련링크(끝부분)
또한 모든 완전수는 삼각수다.
1.2. 완전수의 예
- 6 = 1 + 2 + 3 = 1 + 2 + 3 = 23-21
- 28 = 1 + 2 + 4 + 7 + 14 = 1 + 2 + 3 + ... + 6 + 7 = 25-22
- 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 = 1 + 2 + 3 + ... + 30 + 31 = 29-24
- 8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064 = 1 + 2 + 3 + ... + 126 + 127 = 213-26
[더 보기 · 접기 ]
- 54,162,526,284,365,847,412,654,465,374,391,316,140,856,490,539,031,695,784,603,920,818,387,206,994,158,534,859,198,999,921,056,719,921,919,057,390,080,263,646,159,280,013,827,605,439,746,262,788,903,057,303,445,505,827,028,395,139,475,207,769,044,924,431,494,861,729,435,113,126,280,837,904,930,462,740,681,717,960,465,867,348,720,992,572,190,569,465,545,299,629,919,823,431,031,092,624,244,463,547,789,635,441,481,391,719,816,441,605,586,788,092,147,886,677,321,398,756,661,624,714,551,726,964,302,217,554,281,784,254,817,319,611,951,659,855,553,573,937,788,923,405,146,222,324,506,715,979,193,757,372,820,860,878,214,322,052,227,584,537,552,897,476,256,179,395,176,624,426,314,480,313,446,935,085,203,657,584,798,247,536,021,172,880,403,783,048,602,873,621,259,313,789,994,900,336,673,941,503,747,224,966,984,028,240,806,042,108,690,077,670,395,259,231,894,666,273,615,212,775,603,535,764,707,952,250,173,858,305,171,028,603,021,234,896,647,851,363,949,928,904,973,292,145,107,505,979,911,456,221,519,899,345,764,984,291,328 (무려 770자리 수이다!)}}}
1.3. 홀수 완전수?
메르센 소수가 짝수 완전수와 일대일 대응함을 레온하르트 오일러가 증명했으나, 홀수 완전수는 존재하는지조차 알려지지 않았다. 홀수 완전수가 존재한다면 다음 조건을 만족해야 함이 알려져 있다.
한편, 간단한 증명을 통해 다음 조건을 만족해야 함을 알 수 있다.
- $$p^{4m-3}n^2$$의 꼴로 나타낼 수 있다. 이 때, $$p$$는 4로 나눈 나머지가 1인 소수이고, $$m$$은 자연수이며, $$n$$은 $$p$$와 서로소이고 소인수의 개수가 8개 이상인[7] 홀수다.
...a prolonged meditation on the subject has satisfied me that the existence of any one such '''odd perfect number''' — its escape, so to say, from the complex web of conditions which hem it in on all sides — would be little short of a '''miracle'''.
-
이에 대한 기나긴 명상 끝에 나는 확신했다. '''홀수 완전수'''가 존재한다면 — 모든 방향에서 빈틈없이 감싸는 복잡한 조건들의 그물을 모두 헤치고 빠져나올 수 있다면 — 그것은 거의 '''기적'''이나 마찬가지라고.
1.4. 반완전수
半完全數, Semiperfect number
완전수가 아니지만 진약수의 일부만을 더하면 자기 자신이 되는 수를 말한다. 유사완전수(pseudoperfect number) 라고도 한다. 대표적으로 20이 있다. 20의 진약수들을 모두 더하면 1+2+4+5+10=22이므로 20은 과잉수이지만, 2를 제외한 나머지 진약수들을 더할경우 20(=1+4+5+10)이 되기 때문이다. 반대로, 어떤 진약수들로도 더해서 자기 자신을 만들 수 없는 수는 괴짜수(weird number)라고 한다.
당연히 모든 반완전수는 과잉수[9]이며, 완전수의 배수는 모두 반완전수이다.[10] 그리고 어떤 반완전수는 진약수들의 합으로 표현할 수 있는 방법이 한두 가지밖에 없는 경우도 있지만, 진약수의 일부의 합으로 자기자신이 되도록 하는 방법이 3가지 이상인 것도 있다.
반완전수들의 예시는 다음과 같다. 참고로, 제외할 양의 약수는 취소선으로 표시했다. 또한, 두 가지 이상으로 표시 가능하다면 그중에서 몇 개만 예시로 들어서 표현했다.
- 12 = 1 + 2 + 3 + 6
= 2 + 4 + 6
- 18 = 3 + 6 + 9
- 24 = 4 + 8 + 12
- 30 = 1 + 3 + 5 + 6 + 15
= 5 + 10 + 15
- 36 = 6 + 12 + 18
= 2 + 4 + 12 + 18
= 1 + 2 + 3 + 12 + 18
= 3 + 6 + 9 + 18
= 1 + 2 + 6 + 9 + 18
= 2 + 3 + 4 + 9 + 18
= 2 + 3 + 4 + 6 + 9 + 12
= 1 + 2 + 3 + 12 + 18
= 3 + 6 + 9 + 18
= 1 + 2 + 6 + 9 + 18
= 2 + 3 + 4 + 9 + 18
= 2 + 3 + 4 + 6 + 9 + 12
- 42 = 7 + 14 + 21
- 88 = 1 + 2 + 8 + 11 + 22 + 44
1.4.1. 괴짜수
아이러니하게도, 사실 과잉수 중 반완전수가 아닌 수를 찾기가 더 힘들다. 이러한 수를 weird number(괴짜수, 번역하기에 따라 '운명수'라고도 한다.)라고 하는데, 1만 이하의 수 중 딱 7개 존재한다.[12] 제일 작은 수는 70[13].
단지, $$n$$이 괴짜수인 경우 $$n$$의 약수의 합보다 큰 소수 $$p$$에 대해 $$pn$$이 괴짜수가 되는 성질 때문에, 1만 이상에서는 $$70p$$($$p$$는 144보다 큰 모든 소수)로 인해 갑자기 빈도가 확 늘어난다. 물론 그렇다 해도 빈도가 1%를 넘지 않고, 이는 과잉수의 비율인 25%에 한참 못 미친다. 또한 다른 괴짜수에 의해 이러한 형태로 표현되지 않는 괴짜수는 primitive weird number(원시괴짜수)라고 하며, 백만 이하의 수 중 딱 24개 존재한다.
참고로 현재까지 알려진 괴짜수는 모두 짝수이며, 홀수 괴짜수가 존재하는지는 알려지지 않았다.
1.5. 준완전수
진약수들의 합이 자기 자신이 되지는 않지만 자기 자신의 값과 매우 비슷한 수들을 준완전수라고 부르기도 한다. 그러나 수학적인 의미에서의 준완전수(quasiperfect number)는 보통 진약수의 합이 자기 자신보다 1 큰 수를 가리키는데, 그 이유는 자명하지 않은 약수[14]의 합이 자기 자신이 된다는 의미를 부여할 수 있기 때문이다.
그러나 정의가 무색하게도 현재까지 알려진 준완전수는 '''없다'''. 홀수 완전수 문제와 마찬가지로 정말로 존재하지 않는지 아닌지도 알려져 있지 않다. 해당 문제와 나란히 유클리드 시대에 발견된 이후 정수론 분야에서 제일 오래 된 미해결 문제 중 하나.
1.5.1. Abundance
일반적으로 진약수의 합에서 자기 자신을 뺀 수를 abundance라고 한다.[15] 이 수가 양수이면 과잉수, 0이면 완전수, 음수이면 부족수가 된다. 준완전수는 abundance가 1인 수라고 할 수 있는데 사실 이 abundance가 1을 비롯한 홀수가 되는 경우는 상당히 드물다. 어떤 수 $$n$$의 abundance가 홀수가 되기 위해서는 $$n$$이 제곱수이거나 제곱수와 2의 곱이어야 한다. 그러나 2의 제곱수의 진약수의 합은 항상 자기 자신보다 1 작으므로, abundance가 -1이 아닌 홀수인 수는 반드시 3이상의 홀수의 제곱을 인수로 가져야 하고, 자연수 전체에서 그러한 수의 비율은 매우 낮기 때문이다. 1 이외에도 abundance가 해당 값이 되는 수가 없는 것처럼 보이는 홀수들은 상당히 많으며, 단 하나만 있는 것처럼 보이는 수들이 또한 나머지 중 거의 대부분을 차지한다. 예컨대 18은 abundance가 3인데, abundance가 3인 수는 18 외에는 알려져 있지 않다. -100~100 사이의 100개 홀수 중에서 해당 값을 abundance로 가지는 자연수 $$n$$의 개수가 0인 수(즉, 해당 값을 만족하는 알려진 $$n$$이 없는 수)가 무려 75개, 1개뿐인 수가 22개, 2개인 수가 2개 뿐이다. 유일한 예외는 -1[16].
반면, 짝수라면 상대적으로 홀수보다 빈도가 높아진다. -100~100 사이에서 75%가 0개인 홀수와 달리, 알려진 $$n$$이 없는 짝수는 없다.[17][18] 특히 $$n$$이 완전수인 경우, $$n$$과 서로소인 임의의 소수 $$p$$에 대해 $$pn$$의 abundance는 $$p$$의 값에 상관없이 항상 $$2n$$이 된다. 즉, 임의의 완전수 $$n$$에 대하여 $$2n$$을 자신의 abundance로 가지는 수는 무한히 존재한다. 그것도, 마찬가지로 무한히 존재함을 쉽게 증명할 수 있는 -1보다 훨씬 높은 빈도로. 그리고 $$n$$이 과잉수라면 $$n$$과 서로소인 임의의 소수 $$p$$에 대하여 $$pn$$의 abundance는 $$n$$의 abundance와 $$p$$의 값을 곱한 값에 $$n$$의 약수의 합을 더한 수이고, 만일 $$n$$이 부족수라면 $$n$$의 약수의 합을 abundance의 덧셈 역원으로 나눈 값보다 큰 소수 $$p$$에 대하여 $$pn$$이 부족수가 된다는 성질을 가지고 있다.
참고로, 존재가 알려지지 않은 수 중 절대값이 제일 작은 짝수는 1870이다.[19] 홀수는 물론 준완전수가 되는 1.
2. 문화에서 완전수
특별한 의미를 가져 '완전해진 상태'로 여기는 수를 의미한다. 이런 경우, 종교나 문화에서 찾아 볼 수 있다.
- 3: 동양에서 완전성을 상징한다고 여겨진 수. 3대 요소가 여기에 해당한다. 서양에서는 삼위일체와 같은 형태로 나타난다.
- 7: 성경에서, 여호와가 세상을 창조하고 난 후, 7일 째 휴식하였다.
- 10: 현대에 가장 보편적으로 쓰이는 십진법, 사람의 손가락과 발가락의 개수.
- 12: 12시간, 12개월 등 과거, 현재에도 시간의 단위로 쓰이고 완전수 취급을 받았던 수. 아이러니하게도 이렇게 된 이유가 약수가 많기 때문, 즉 과잉수이기 때문이다.
2.1. 불완전수
반대 개념으로 '불완전수'가 있다. 불완전수는 부족수와 과잉수로 분류된다. 대표적으로 6은 7에서 1이 부족한 '부족수'이며, 13은 12에 1을 더한 '과잉수'이다.
[1] $$2^n-1$$이 소수가 아닐 경우 해당 수는 과잉수가 된다.[2] 왜냐하면, 짝수 완전수는 계속 반으로 쪼개다보면 결국 메르센 소수가 나오는데, 이 소수와 대응하는 수를 만들기 위해서는 '2의 거듭제곱 - 1'이 필요하기 때문이다.[2] 오일러가 처음 증명했으니 증명이 무지하게 어려울 거라고 생각하기 쉬운데, 의외로 그다지 어렵지 않으므로 완전수에 관심 있는 위키러는 한 번 연습삼아 시도해보자.[3] 컴퓨터로 모조리 뒤졌다.[4] $$10^8$$ 미만의 모든 소수 조합을 모조리 뒤졌다.[5] 100개 소수 곱으로 표현 가능한 조합 패턴을 모조리 뒤졌다.[6] 소인수 8개인 경우를 패턴화하여 모조리 뒤졌다.[7] 여기만 증명이 어렵다.[8] 위 방법들을 확장해 조합에 들어가는 가짓수를 늘린 뒤 증명하는 건 어렵지 않아 보이는데, 가짓수 자체가 무한해서 노가다로 방법이 없다. 어떤 의미에서 1900년 초의 페르마의 마지막 정리와 비슷한 상태. [9] 진약수들의 합이 자기 자신보다 큰 수[10] 예를 들면 $$6a$$($$a$$는 1보다 큰 정수)의 경우 $$a+2a+3a=6a$$이므로 반완전수다.[11] 945는 가장 작은 홀수 과잉수이기도 하다.[12] 70, 836, 4030, 5830, 7192, 7912, 9272[13] 70의 약수는 1, 2, 5, 7, 10, 14, 35, 70으로, 70을 제외한 약수의 합은 74이다. 하지만 위 약수들 중 어떤 조합을 제외해도 합이 70이 되도록 할 수는 없다. 5 이상의 수는 아예 뺄 수 없고, 나머지는 1, 2 뿐이어서 둘 모두를 빼도 71이기 때문.[14] 모든 자연수는 1과 자기 자신을 약수로 가지며, 이 둘을 제외한 약수는 자명하지 않은 약수이다.[15] 우리말로 할 경우 과잉값 혹은 과잉도 정도로 번역될 수 있다. [16] 상술했다시피 모든 2의 제곱수가 해당한다.[17] 1개인 수는 종종 있다.[18] 모든 짝수에 대해 이러한 $$n$$이 있는지는 알려지지 않았다. 이를 흔히 강한 골드바흐 추측(8 이상의 모든 짝수는 '''서로 다른''' 두 소수의 합으로 표현된다는, 볼드체 부분이 없는 원래 골드바흐 추측보다 조금 더 강한 조건의 추측. 당연하지만 아직 증명되지 않았다.)과 연결된 문제라고 착각하는데, 해당 문제는 진약수의 합의 값의 존재성에 관련된 것이며, 이 문제와는 다르다. 불가촉 수 문서 참고.[19] 주어진 홀수 $$n$$에 대해 $$2^k-n$$이 소수가 되는 $$k$$가 존재할 경우, abundance가 $$n-1$$이 되는 수가 존재함이 알려져 있다. $$n$$은 홀수여야 하므로, 이 성질을 이용해 대부분의 짝수 케이스는 찾을 수 있다. 문제는 그러한 $$k$$가 없는 $$n$$이 종종 있다는 것과, 그 역은 성립하지 않는다는 것.