mir.pe (일반/어두운 화면)
최근 수정 시각 : 2024-11-25 09:14:34

완전수

정수론
Number Theory
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px" 		공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질
산술
나눗셈 약수· 배수 배수 · 약수( 소인수) · 소인수분해( 목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론( 국소체) · 해석적 정수론
산술함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

약수의 합에 따른 자연수의 분류
Divisibility-based sets of integers
{{{#!wiki style="margin:0 -10px -5px; min-height:calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-5px -1px -11px; word-break: keep-all" 		<colbgcolor=#c1a470><colcolor=#fff> 자기 자신과의 비교 과잉수 완전수 부족수
일부의 합 사슬 주기 1 주기 2 주기 3 이상
진약수의 합 완전수 <colbgcolor=#fff,#1c1d1f> 친화수 <colbgcolor=#ddd,#333> 사교수
비자명 진약수의 합 <colbgcolor=#000> 준완전수 혼약수 준사교수
진약수의 합의 약수 초완전수 ? ?
기타 반완전수 괴짜수 불가촉 수 }}}}}}}}}


1. 수학에서 완전수
1.1. 개요1.2. 완전수의 예1.3. 홀수 완전수?1.4. 반완전수
1.4.1. 괴짜수
1.5. 준완전수
1.5.1. abundance
2. 문화에서 완전수
2.1. 불완전수

1. 수학에서 완전수

1.1. 개요

完 全 數 / perfect number

완전수란, 자기 자신을 제외한 약수(진약수)들의 합이 자기 자신이 되는 수를 말한다. 예를 들어, 6의 약수는 자기 자신인 6을 제외한 1, 2, 3이고 진약수들의 합은 1 + 2 + 3 = 6, 즉 자기 자신이므로 6은 완전수다.

수학적으로 표현하면, 다음 식을 만족시키는 자연수 [math(n)]을 완전수라고 한다. 여기서 [math(\sigma_1(n))]은 약수 함수(divisor function)이다.

[math(\sigma_1(n)=2n)]

6, 28, 496, 8128 등이 있다. 이러한 규칙성에 따라 다섯 번째로 6으로 끝나는 5자리 완전수가 존재할 것이라 예상되기도 했었으나 다음 완전수는 33550336이다. 6으로 끝나긴 하지만 8자리. 6번째 완전수는 8589869056으로 6, 8이 교대해서 나타날 것이라는 예측도 빗나갔다. 조금 더 확장하면, 짝수 완전수의 가장 끝의 자리 수는 6 또는 28로 나타남이 증명되어 있다.

짝수 완전수들은 모두 [math(2^{n-1}(2^n-1))] ([math(2^n-1)]은 소수)의 형태로, 이를 레온하르트 오일러가 증명했다.[1][2][3] 이때, 이 소수인 [math(2^n-1)]을 메르센 소수라 한다. 따라서 메르센 소수와 짝수 완전수는 일대일 대응이고 모든 짝수 완전수는 소인수의 개수가 2개로, 2와 [math(2^n-1)]을 소인수로 가지게 된다.

또한 모든 짝수 완전수는 메르센 소수번째 삼각수다. 즉 모든 짝수 완전수는 1부터 2n-1까지의 모든 자연수의 합으로 표현될 수 있으며, 2의 지수가 n-1, (2n-1)에 해당하는 메르센 소수의 지수가 1이므로 제곱수가 아니다. 또한 6을 제외한 모든 완전수는 1부터 연속된 홀수의 세제곱의 합이기도 하다.

메르센 소수의 수가 유한한지 무한한지는 알려져 있지 않으므로 짝수 완전수의 유, 무한 여부도 알려져 있지 않다. 또한 홀수 완전수가 존재하는지 여부도 알려져 있지 않다. 그러나 만약 홀수 완전수가 존재한다면, 그 수는 최소 101500 이상인 것으로 알려져 있다.

관련 링크 (끝부분)

1.2. 완전수의 예

[더 보기 · 접기 ]
* 33,550,336 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 + 2048 + 4096 + 8191 + 16382 + 32764 + 65528 + 131056 + 262112 + 524224 + 1048448 + 2096896 + 4193792 + 8387584 + 16775168 = 1 + 2 + 3 + ... + 8190 + 8191 = 225-212
  • 8,589,869,056 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1,024 + 2,048 + 4,096 + 8,192 + 16,384 + 32,768 + 65,536 + 131,071 + 262,142 + 524,284 + 1,048,568 + 2,097,136 + 4,194,272 + 8,388,544 + 16,777,088 + 33,554,176 + 67,108,352 + 134,216,704 + 268,433,408 + 536,866,816 + 1,073,733,632 + 2,147,467,264 + 4,294,934,528
  • 137,438,691,328 = 218×524287
  • 2,305,843,008,139,952,128 = 230×2147483647
  • 2,658,455,991,569,831,744,654,692,615,953,842,176
  • 191,561,942,608,236,107,294,793,378,084,303,638,130,997,321,548,169,216
  • 13,164,036,458,569,648,337,239,753,460,458,722,910,223,472,318,386,943,117,783,728,128
  • 14,474,011,155,664,524,427,946,373,126,085,988,481,573,677,491,474,835,889,066,354,349,131,199,152,128
  • 23,562,723,457,267,347,065,789,548,996,709,904,988,477,547,858,392,600,710,143,027,597,506,337,283,178,622,239,730,365,539,602,600,561,360,255,566,462,503,270,175,052,892,578,043,215,543,382,498,428,777,152,427,010,394,496,918,664,028,644,534,128,033,831,439,790,236,838,624,033,171,435,922,356,643,219,703,101,720,713,163,527,487,298,747,400,647,801,939,587,165,936,401,087,419,375,649,057,918,549,492,160,555,646 (무려 314자리 수이다.)
  • 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. 홀수 완전수?

메르센 소수가 짝수 완전수와 일대일 대응함을 레온하르트 오일러가 증명했으나, 홀수 완전수는 존재하는지조차 알려지지 않았다. 홀수 완전수 N이 존재한다면 다음 조건을 만족해야 함이 알려져 있다. 이처럼 조건들이 너무나도 까다롭기에 현재 수학자들도 홀수 완전수가 없을 것으로 추측하고 있다. 위 방법들을 확장해 조합에 들어가는 가짓수를 늘린 뒤 증명하는 건 어렵지 않아 보이는데, 가짓수 자체가 무한해서 노가다로 방법이 없다. 어떤 의미에서 1900년 초의 페르마의 마지막 정리와 비슷한 상태. 만약 존재한다면 기하나 미적분 같은 어려운 수능 문제조차도 한참 뛰어넘는 어마무시한 적들을 모두 물리친 아름답고도 완벽한 수라고... 1888년, 수학자 실베스터(Sylvester)는 다음과 같은 말을 남겼다.
...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)라고 한다.

당연히 모든 반완전수는 과잉수이며, 완전수 및 반완전수의 배수는 모두 반완전수다.[8] 그리고 어떤 반완전수는 진약수들의 합으로 표현할 수 있는 방법이 한두 가지밖에 없는 경우도 있지만, 진약수의 일부의 합으로 자기자신이 되도록 하는 방법이 3가지 이상인 것도 있다.

반완전수들의 예시는 다음과 같다. 참고로, 제외할 양의 약수는 취소선으로 표시했다. 또한, 2가지 이상으로 표시 가능하다면 그중에서 몇 개만 예시로 들어서 표현했다.
홀수인 반완전수 중 제일 작은 수는 945이다.[9] 945 = 1 + 3 + 5 + 7 + 9 + 15 + 21 + 27 + 35 + 45 + 63 + 105 + 135 + 189 + 315가 되어[10] 반완전수의 조건을 만족한다. 그리고 홀수 과잉수는 현재까지 모두 반완전수에 속한다고 알려져 있다.

1.4.1. 괴짜수

weird number

반완전수의 정의에서 찾을 수 있는 직관적인 주제와 달리, 사실 과잉수 중 반완전수가 아닌 수를 찾기가 훨씬 더 힘들다. 이러한 수를 괴짜수[11]라고 하는데, 1만 이하의 수 중 딱 7개 존재한다.[12] 괜히 이상한(weird) 수라고 명명된 게 아닌 셈. 제일 작은 괴짜수는 70[13]이다.

단지, [math(n)]이 괴짜수인 경우 [math(n)]의 약수의 합보다 큰 소수 [math(p)]에 대해 [math(pn)]이 괴짜수가 되는 성질 때문에, 1만 이상에서는 10430[14]을 시작으로 [math(70p)]([math(p)]는 144보다 큰 모든 소수)로 인해 갑자기 빈도가 확 늘어난다[15]. 물론 그렇다 해도 빈도가 1%를 넘지 않고, 이는 과잉수의 비율인 25%에 한참 못 미친다. 또한 다른(더 작은) 괴짜수에 의해 이러한 형태로 표현되지 않는 괴짜수는 primitive weird number(원시괴짜수)라고 하며, 백만 이하의 수 중 딱 24개 존재한다.

현재까지 알려진 괴짜수는 모두 짝수이며, 홀수 괴짜수가 존재하는지는 알려지지 않았다. 또한 위의 성질에서 괴짜수는 무한히 존재하고, 홀수 괴짜수 또한 만약 존재한다면 무한히 존재함을 알 수 있는데, 원시괴짜수의 경우 무한히 존재한다고 추측하지만 아직 증명되지는 않았다.

1.5. 준완전수

진약수들의 합이 자기 자신이 되지는 않지만 자기 자신의 값과 매우 비슷한 수[16]들을 준완전수라고 부르기도 한다. 그러나 수학적인 의미에서의 준완전수(quasiperfect number)는 보통 진약수의 합이 자기 자신보다 1 큰 수를 가리키는데, 그 이유는 자명하지 않은 약수[17]의 합이 자기 자신이 된다는 의미를 부여할 수 있기 때문이다.

그러나 정의가 무색하게도 현재까지 알려진 준완전수는 없다. 홀수 완전수 문제와 마찬가지로 정말로 존재하지 않는지 아닌지도 알려져 있지 않다. 해당 문제와 나란히 유클리드 시대에 발견된 이후 정수론 분야에서 제일 오래 된 미해결 문제 중 하나. 존재한다면 아래와 같은 조건들을 충족해야 함이 알려져 있다.
이와 비슷하게 진약수의 합이 자기 자신보다 1 작은 수를 태완전수[19](almost-perfect number)라고 한다. 준완전수와 달리 많이 존재하며, 대표적으로 음이 아닌 정수에 대한 2의 거듭제곱수들(1, 2, 4, 8, 16, ...)이 있다. 그러나 이러한 꼴이 아닌 태완전수의 존재 여부는 알려지지 않았다.

1.5.1. abundance

일반적으로 진약수의 합에서 자기 자신을 뺀 수를 abundance라고 한다.[20] 즉, 주어진 자연수 [math(n)]에 대한 abundance [math(a(n))][21]은,

[math(a(n)=s(n)-n=\sigma_1(n)-2n)]

이다. 즉, 가 된다.

주어진 [math(n)]에 대해 [math(k=a(n))]을 만족하는 [math(k)]를 구하는 것은 유한한 시간 내에 반드시 가능하지만, 이 함수의 역함수, 즉 주어진 [math(k)]에 대해 [math(k=a(n))]을 만족하는 [math(n)]을 구하는 것은 가능할지 알 수 없는 때가 많다. 홀수 완전수나 준완전수 등의 존재성 문제를 일반화한다는 것은 결국 이 역함수의 특성을 해명하는 것으로 이해할 수 있다. 아래는 [math(a(n))]과 [math(a^{-1}(k)=\{n|a(n)=k\})]의 알려진 특성들이다.

2. 문화에서 완전수

특별한 의미를 가져 '완전해진 상태'로 여기는 수를 의미한다. 이런 경우, 종교나 문화에서 찾아 볼 수 있다.

2.1. 불완전수

반대 개념으로 '불완전수'가 있다. 불완전수는 부족수와 과잉수로 분류된다.

[1] 이 사실은 유클리드시절부터 알려진 성질이다. [2] [math(2^n-1)]이 소수가 아니면 과잉수가 된다. [3] 왜냐하면, 짝수 완전수는 계속 반으로 쪼개다보면 결국 메르센 소수가 나오는데, 이 소수와 대응하는 수를 만들려면 ' 2의 거듭제곱 - 1'이 필요하기 때문이다. 오일러가 처음 증명했으니 증명이 무지하게 어려울 거라고 생각하기 쉬운데, 의외로 그다지 어렵지 않다. [4] 이보다 작은 홀수는 모두 완전수가 아님을 컴퓨터로 확인했다. [5] [math(10^8)] 미만의 모든 소수 조합을 전부 확인했다. [6] 100개의 소수 곱으로 표현 가능한 조합 패턴을 전부 확인했다. [7] 소인수 9가지 이하인 경우를 패턴화하여 전부 확인했다. [8] 예를 들면 [math(ak)]([math(k)]는 완전수 혹은 반완전수이고 [math(a)]는 1보다 큰 정수)의 경우 [math(k=b_1+b_2+...+b_n)]를 만족하는 [math(k)]의 약수 부분집합에 대해 [math(ab_1+ab_2+...+ab_n=ak)]이고 각 항은 모두 [math(ak)]의 서로 다른 약수이므로 반완전수다. [9] 945는 가장 작은 홀수 과잉수이기도 하다. [10] 9와 21 대신 3과 27을 제외하고 모두 더해도 된다. 사실 제외할 진약수의 일부의 합이 abundance의 값과 같은 값이 되는 조합이라면 모두 가능해서 1, 5, 9, 15나 3, 5, 7, 15 혹은 1, 3, 5, 21을 제외하고 합해도 같으므로 상관은 없다. [11] 번역하기에 따라 '기묘수', '운명수'라고도 한다. [12] 70, 836, 4030, 5830, 7192, 7912, 9272 [13] 70의 약수는 1, 2, 5, 7, 10, 14, 35, 70으로, 70을 제외한 약수의 합은 74이다. 하지만 위 약수들 중 어떤 조합을 제외해도 합이 70이 되도록 할 수 없다. 5 이상의 수를 빼면 합이 70보다 작아지고, 4만큼의 숫자가 빠져야 하는데, 나머지는 1, 2 뿐이라 합이 3이어서 둘 모두를 빼도 71이기 때문. [14] 70 × 149(소수) [15] 17272보다 큰 괴짜수 중 70의 배수를 제외하고 제일 작은 건 45356이다. [16] 비율로 따지자면 abundance의 값이나 이에 부호가 바뀐 반수가 자기자신의 10% 이내인 수. [17] 모든 자연수는 1과 자기 자신을 약수로 가지며, 이 둘을 자명 약수, 이 둘을 제외한 약수, 즉 진약수 중 1을 제외한 수는 자명하지 않은 약수이다. 모든 소수는 진약수가 1밖에 없으므로 자명하지 않은 약수가 존재하지 않는다. [18] 증명 [19] 위태, 태반 등에 쓰이는 殆(거의 태) 자를 쓰며, 중국의 용어로 한국의 정식 용어는 아니다. [20] 우리말로 할 경우 과잉값 혹은 과잉도 정도로 번역될 수 있다. 어번던수 [21] 공식 표기는 아니다. [22] [math(a^{-1}(-1)\supset\{2^n|n\geq 0\})] [23] [math(a^{-1}(2n)\supset\{pn\})], [math(p)]는 [math(n)]의 약수가 아닌 소수. [24] 즉 [math(a^{-1}(k))]의 원소가 존재하지 않는다고 확인된 [math(k)]는 없다. 또한 모든 짝수 [math(k)]에 대해서도 [math(k=a(n))]을 만족하는 [math(n)]이 있는지는 알려지지 않았다. 이를 흔히 강한 골드바흐 추측(8 이상의 모든 짝수는 서로 다른 두 소수의 합으로 표현된다는, 볼드체 부분이 없는 원래 골드바흐 추측보다 조금 더 강한 조건의 추측. 당연하지만 아직 증명되지 않았다.)과 연결된 문제라고 착각하는데, 해당 문제는 진약수의 합의 값의 존재성에 관련된 것이며, 이 문제와는 다르다. 불가촉 수 문서 참고. [25] [math(a(n))]이 홀수가 되기 위해서는 [math(n)]이 제곱수이거나 제곱수와 2의 곱이어야 한다. 그러나 2의 제곱수의 진약수의 합은 항상 자기 자신보다 1 작으므로, abundance가 -1이 아닌 홀수인 수는 반드시 3이상의 홀수의 제곱을 인수로 가져야 하고, 자연수 전체에서 그러한 수의 비율은 매우 낮기 때문이다. 1 이외에도 [math(a^{-1}(k))]의 원소가 발견되지 않은 홀수들은 상당히 많으며, 단 하나만 있는 것처럼 보이는 수들이 또한 나머지 중 거의 대부분을 차지한다. 예컨대 [math(a^{-1}(3))]은 18 외에는 알려져 있지 않다. -100~100 사이의 100개 홀수 중에서 해당 값을 abundance로 가지는 자연수 [math(n)]의 개수가 0인 수(즉, 해당 값을 만족하는 알려진 [math(n)]이 없는 수)가 무려 75개, 1개뿐인 수가 22개, 2개인 수가 2개 뿐이다. 유일한 예외는 상술했다시피 모든 2의 제곱수가 해당하는 -1. [26] 즉 그러한 [math(k)]가 존재할 경우, abundance가 [math(n-1)]이 되는 수가 존재한다고 할 수 있으며, 실제 짝수에서 발견되는 상당수의 원소가 이러한 형태로 표현된다. [math(n)]이 1인 경우가 완전수 케이스. [math(n)]은 홀수여야 하므로, 이 성질을 이용해 대부분의 짝수 케이스는 찾을 수 있다. 문제는 그러한 [math(k)]가 없는 [math(n)]이 종종 있다는 것과, 그 역은 성립하지 않는다는 것. 예컨대 언급한 1870의 경우, [math(2^k-1871)]이 소수가 되는 [math(k)]는 현재까지 발견되지 않았고, [math(2^k-777149)]의 경우에는 심지어 그러한 [math(k)]가 존재하지 않는다는 사실이 확인되었다. 물론 그러한 k가설령 존재하지 않는다고 해서 abundance가 1870인 수는 존재하지 않는다고 할 순 없다. 예컨대 [math(a(8925)=6)]이지만 [math(2^k-7)]이 소수가 되는 가장 작은 [math(k)]는 무려 39이다.

분류