자기 자신을 제외한 양의 약수를 모두 더했을 때 원래 수가 되는 자연수를 완전수라고 합니다. 6의 진약수는 1,2,3이고 합이 6입니다. 28의 진약수 1,2,4,7,14의 합도 28입니다. 유클리드는 2^p−1이 소수이면 N=2^(p−1)(2^p−1)이 완전수라는 구성을 증명했습니다. 오일러는 모든 짝수 완전수가 이 형태라는 역방향을 증명했습니다.
완전수와 약수 함수의 정의
σ(n)을 n의 양의 약수를 자기 자신까지 포함해 모두 더한 약수합 함수라고 하겠습니다. 진약수의 합은 s(n)=σ(n)-n입니다. 완전수 조건 s(n)=n은 σ(n)=2n과 같습니다. 과잉수는 s(n)>n, 부족수는 s(n)<n입니다.
n이 완전수 ⇔ s(n)=n ⇔ σ(n)=2n
| n | 진약수 | 진약수 합 | 분류 |
|---|---|---|---|
| 6 | 1,2,3 | 6 | 완전수 |
| 12 | 1,2,3,4,6 | 16 | 과잉수 |
| 15 | 1,3,5 | 9 | 부족수 |
| 28 | 1,2,4,7,14 | 28 | 완전수 |
메르센 수와 메르센 소수
M_p=2^p−1 형태의 수를 메르센 수라고 합니다. 그 값이 소수이면 메르센 소수입니다. p=2이면 3, p=3이면 7, p=5이면 31, p=7이면 127이 소수입니다. p=11에서는 2^11−1=2047=23×89이므로 소수가 아닙니다. 지수 p가 소수라고 해서 M_p가 반드시 소수인 것은 아닙니다.
반대로 2^p−1이 소수라면 p는 소수여야 합니다. p=ab가 합성수라면 2^{ab}−1=(2^a−1)(1+2^a+…+2^{a(b−1)})로 인수분해되기 때문입니다. 따라서 p의 소수성은 필요한 조건이지만 충분조건은 아닙니다.
유클리드 공식으로 28 만들기
p=3이면 2^3−1=7이 소수입니다. 공식에 넣으면 N=2^(3−1)×7=4×7=28입니다. 28의 진약수를 더하면 1+2+4+7+14=28입니다. p=5이면 N=2^4×31=496, p=7이면 2^6×127=8128이 됩니다.
| p | M_p=2^p−1 | 완전수 2^(p−1)M_p |
|---|---|---|
| 2 | 3 | 6 |
| 3 | 7 | 28 |
| 5 | 31 | 496 |
| 7 | 127 | 8,128 |
| 13 | 8,191 | 33,550,336 |
공식이 완전수를 만드는 증명
M=2^p−1이 소수라고 하겠습니다. N=2^(p−1)M에서 2^(p−1)과 M은 서로소입니다. 약수합 함수는 서로소인 두 수의 곱에서 곱셈적이므로 σ(N)=σ(2^(p−1))σ(M)입니다.
σ(2^(p−1))=1+2+…+2^(p−1)=2^p−1=M
σ(M)=1+M=2^p
따라서 σ(N)=M×2^p입니다. 한편 2N=2×2^(p−1)M=2^pM이므로 σ(N)=2N입니다. 완전수 조건과 정확히 같습니다. M이 소수라는 조건 덕분에 M의 약수가 1과 M뿐이어서 σ(M)=1+M을 쓸 수 있습니다.
모든 짝수 완전수도 이 형태입니다
오일러가 증명한 역방향과 합치면 유클리드–오일러 정리가 됩니다. 짝수 완전수 N은 반드시 N=2^(p−1)(2^p−1) 꼴이고 2^p−1은 소수입니다. 즉 짝수 완전수를 찾는 문제는 메르센 소수를 찾는 문제와 일대일로 연결됩니다.
역방향의 핵심은 N=2^k m에서 m을 홀수로 두고 σ(N)=2N을 이용하는 것입니다. σ(2^k)=2^(k+1)−1이고 서로소 곱의 약수합 성질을 적용하면 홀수 부분 m의 약수 구조가 강하게 제한됩니다. 결국 m=2^(k+1)−1이 소수이고 p=k+1인 형태만 남습니다.
약수합 함수가 곱으로 분리되는 이유
서로소인 양의 정수 a,b의 모든 약수는 a의 약수 하나와 b의 약수 하나를 곱한 꼴로 유일하게 나타납니다. 그래서 σ(ab)=σ(a)σ(b)가 성립합니다. 이를 약수합 함수의 곱셈성이라고 합니다. N=2^(p−1)M_p에서는 2의 거듭제곱과 홀수 M_p가 서로소이므로 이 성질을 바로 적용할 수 있습니다.
일반적으로 n=q₁^a₁q₂^a₂…qᵣ^aᵣ처럼 소인수분해되면 σ(n)=∏(1+qᵢ+qᵢ²+…+qᵢ^aᵢ)입니다. 각 괄호는 하나의 소인수에서 선택할 수 있는 지수를 모두 더한 것입니다. 완전수 공식의 증명은 이 일반식에서 M_p의 지수가 1이고 M_p 자체가 소수인 특별한 경우입니다.
홀수 완전수는 아직 발견되지 않았습니다
모든 완전수가 짝수라는 증명은 없습니다. 홀수 완전수가 존재하는지 여부는 오래된 미해결 문제입니다. 존재한다고 가정할 때 소인수의 개수, 합동식과 최소 크기에 관한 강한 필요조건들이 알려져 있지만 존재도 부존재도 증명되지 않았습니다. ‘알려진 완전수는 모두 짝수’와 ‘모든 완전수는 짝수’는 다른 문장입니다.
완전수의 이진 표현
N=2^(p−1)(2^p−1)은 이진법에서 p개의 1 뒤에 p−1개의 0이 붙은 모양입니다. 28은 11100₂, 496은 111110000₂입니다. 2^p−1이 이진법으로 p개의 1이고 2^(p−1)을 곱하면 왼쪽으로 p−1칸 이동하기 때문입니다.
메르센 소수 판정
매우 큰 M_p가 소수인지 일반적인 나눗셈으로 확인하기는 어렵습니다. 메르센 수에는 루카스–레머 검사가 사용됩니다. p가 홀수 소수일 때 s₀=4, s_{k+1}=s_k²−2를 M_p로 나눈 나머지로 계산하고 s_{p−2}=0이면 M_p는 소수입니다. 이 검사는 특정 메르센 수 형태에 맞춘 결정적 판정법입니다.
새 메르센 소수 발견 발표는 서로 다른 하드웨어와 프로그램의 독립 검증을 거칩니다. 큰 수 계산은 메모리 오류나 구현 오류가 있을 수 있기 때문입니다. 메르센 수 후보의 지수 p가 소수인지 먼저 확인하고 루카스–레머 검사를 수행합니다.
완전수의 자릿수는 어떻게 계산할까
N=2^(p−1)(2^p−1)의 십진 자릿수는 ⌊log₁₀N⌋+1입니다. 큰 p에서는 log₁₀N=(p−1)log₁₀2+log₁₀(2^p−1)을 계산하면 거대한 정수를 전부 십진수로 펼치지 않고도 자릿수를 알 수 있습니다. 2^p−1은 2^p에 매우 가까우므로 완전수의 자릿수는 대략 ⌊(2p−1)log₁₀2⌋+1로 예상할 수 있지만, 정확한 값은 원래 로그식으로 판정해야 합니다.
완전수와 대응하는 메르센 소수는 같은 지수 p를 공유하지만 크기는 크게 다릅니다. M_p는 약 2^p이고 완전수 N은 약 2^(2p−1)이므로 N은 M_p의 제곱의 절반 정도입니다. 메르센 소수 기록이 갱신될 때 대응하는 완전수는 훨씬 더 많은 자릿수를 갖게 됩니다.
짝수 완전수에서 바로 따라오는 성질
p>2인 메르센 소수 지수는 홀수입니다. 이때 짝수 완전수 N=2^(p−1)(2^p−1)은 2^(p−1)로 나누어지고 p−1은 짝수이므로 N은 적어도 4의 배수입니다. 또 N을 삼각수로 쓰면 N=T_(2^p−1)입니다. 실제로 T_(2^p−1)=(2^p−1)2^p/2=2^(p−1)(2^p−1)이기 때문입니다.
짝수 완전수는 육각수이기도 합니다. k번째 육각수 H_k=k(2k−1)에 k=2^(p−1)을 넣으면 H_k=2^(p−1)(2^p−1)=N입니다. 따라서 6, 28, 496, 8128은 약수합 조건뿐 아니라 도형수의 교차점이라는 성질도 가집니다. 이 결론은 완전수 공식에서 대수적으로 따라오는 정리이며 수치 관찰만으로 얻은 추측이 아닙니다.
완전수와 친화수의 차이
완전수는 자신의 진약수 합이 자신으로 돌아오는 주기 1 구조입니다. 친화수 a,b는 s(a)=b와 s(b)=a를 만족하는 주기 2 구조입니다. 220과 284가 대표적인 친화수 쌍입니다. 둘 다 약수합 함수를 사용하지만 같은 개념은 아닙니다.
자주 생기는 오해
- 공식은 2p−1(2p−1)이 아니라 2^(p−1)(2^p−1)입니다.
- p가 소수여도 2^p−1이 합성수일 수 있습니다. p=11이 반례입니다.
- 유클리드–오일러 정리는 짝수 완전수를 완전히 분류하지만 홀수 완전수 문제를 해결하지 않습니다.
- 완전수라는 이름은 근삿값이 완벽하다는 뜻이 아니라 진약수 합 조건을 가리킵니다.
- 알려진 메르센 소수의 개수와 최대 기록은 새 발견에 따라 바뀌므로 최신 목록은 공식 프로젝트에서 확인해야 합니다.
완전수와 메르센 소수 핵심 정리
2^p−1이 소수이면 N=2^(p−1)(2^p−1)은 σ(N)=2N을 만족해 완전수가 됩니다. 약수합 함수의 곱셈성과 등비수열 합으로 이를 바로 계산할 수 있습니다. 오일러의 역정리에 따라 모든 짝수 완전수는 반드시 이 형태입니다.
메르센 소수를 하나 찾으면 짝수 완전수 하나를 얻습니다. 다만 소수 지수 p가 항상 메르센 소수를 만드는 것은 아니며, 홀수 완전수의 존재 여부는 여전히 미해결입니다. 증명된 짝수 분류와 미해결인 홀수 문제를 구분해야 합니다.