과잉수
1. 개요
過剩數, Abundant number
자연수 $$n$$에 대하여, $$n$$의 모든 진약수[1]들의 합이 $$n$$보다 크면 $$n$$을 과잉수라고 한다. 즉, 약수의 합이 $$2n$$보다 크면 과잉수인 것이다. 약수 함수(divisor function)를 이용해 나타내면 다음을 만족하는 자연수 $$n$$을 말한다.
$$n<\sigma_1\left(n\right)-n$$[2]
또는 이 식을 변형하여 다음과 같이 나타낼 수 있다.
$$2n<\sigma_1\left(n\right)$$
2. 성질
- 소수는 (진약수가 1밖에 없으므로) 모두 부족수이고[3] 1도 (그야 당연히 진약수가 없으니까) 부족수이므로 과잉수는 모두 합성수다.('합성수는 모두 과잉수다.'는 거짓인데, 6과 28은 합성수이지만, 과잉수가 아니다. 또한 110같은 경우에는 합성수이지만, 부족수다.)
- 가장 작은 과잉수는 12이며 가장 작은 홀수[4]인 과잉수는 945이다[5].
- 과잉수 중 진약수의 일부의 합이 자기자신과 같아지는 것은 반완전수이고[6], 진약수의 일부를 더해도 자기자신을 나타낼 수 없으면 괴짜수이다.
- 자기 자신을 제외한 완전수, 과잉수의 배수는 모두 과잉수이다. 그러므로 과잉수는 무한히 많다. 예를 들어 완전수인 6의 경우, 6을 제외한 6의 배수는 모두 과잉수이다[7]. 그리고 진약수들이 모두 부족수인 과잉수 즉 다른 과잉수 또는 완전수의 자기자신이 아닌 배수들로 표기될 수 없는 과잉수는 primitive abundant number[8]라고 하며, 1000 이하의 수 중 딱 16개 존재한다. 원시 과잉수 역시 무한히 많다. 또한, 완전수까지 포함한다면 총 19개가 있다. 이들 중 17개는 (반)완전수이고, 나머지 둘(70, 836)은 괴짜수이다. 마찬가지로 어떤 반완전수의 진약수에 반완전수가 전혀 없어서 모두 부족수, 또는 괴짜수와 부족수이더라도 일부 진약수의 합이 자기자신이 되면 그 반완전수는 primitive semiperfect number[9]이다.
- 완전수 또는 과잉수 n의 약수(총 k개)를 각각 n1, n2, ..., nk라 하면 n은 완전수 또는 과잉수이므로 n1+n2+...+nk≥2n이다. m이 자연수일 때, 이들 각각에 m을 곱한 m×n1, m×n2, ..., m×nk는 mn의 약수이고 (m×n1)+(m×n2)+...+(m×nk)=m×(n1+n2+...+nk)≥2mn이다. m>1이면 이 외에 1도 약수이고, 1은 (m×na)(a는 1≤a≤k인 자연수) 꼴로 나타낼 수 없으므로 mn의 모든 약수의 합은 최소 2mn+1로 2mn보다 크다. 따라서 m>1이거나, 즉 완전수 또는 과잉수의 2배, 3배, ...이거나 n이 과잉수이면 mn은 과잉수이며, 완전수인 경우는 완전수의 1배인 경우뿐이다.
2.1. 과잉수의 합과 차로 표현되는 정수
여기서 a, b는 2 이상의 자연수이다.
- 20161보다 큰 모든 정수는 2개의 과잉수의 합으로 표현할 수 있다. 예를 들어 20163은 945+19218, 1575+18588, 2205+17958 등으로 나타낼 수 있다.
- 6을 제외한 6의 배수는 모두 과잉수이므로, 6으로 나눈 나머지 r에 따라 n보다 크면 항상 2개의 과잉수의 합으로 표현할 수 있는 n이 서로 다르다. 다른 과잉수인 20, 56 등도 마찬가지이다. 또, 992 이상의 자연수는 2개 이상의 과잉수의 합으로 표현할 수 있다.
- r=0이면 6의 배수이므로, 6a+6b 꼴로 나타낼 수 있는 최소의 수인 24 이상이면 2개의 과잉수의 합으로 나타낼 수 있다.
- r=1이면 945+40=985는 2개의 과잉수의 합으로 표현되지만 991, 997 등은 그렇지 않다. 마찬가지로 r=5이면 945+20=965는 2개의 과잉수의 합으로 표현되지만 971은 그렇지 않다.[10] 따라서 r=1 또는 5인 경우 나머지 경우보다 n이 크다. 3개의 과잉수의 합으로는 r=1일 때 (945+40+6a 또는 945+20+20+6a)=997 이상[11], r=5일 때 945+20+6b=977 이상[12]이면 표현 가능하다.
- r=2이면 20은 과잉수이므로, 20+6a 꼴로 나타낼 수 있는 최소의 수인 32 이상이면 된다.
- r=3이면 945는 과잉수이므로, 945+6a 꼴로 나타낼 수 있는 최소의 수인 957 이상이면 된다.
- r=4이면 40은 과잉수이므로, 40+6a 꼴로 나타낼 수 있는 최소의 수인 52 이상이면 된다.
- 모든 정수는 두 과잉수의 차(두 과잉수 x, y에 대하여 x-y)로 표현될 수 있는데, 6으로 나눈 나머지가 1인 최소의 과잉수인 5391411025(X라 하자.)와 어떤 과잉수의 배수와 완전수의 2, 3, 4, ...배는 항상 과잉수라는 것을 이용하면 된다. 6으로 나눈 나머지가 r(r=0, 1, 2, 3, 4, 5)인 모든 정수는 다음과 같이 두 과잉수의 차로 나타낼 수 있다. 이를 절댓값 처리한 |x-y|에 대해서도 마찬가지로 하면 된다.
- r=0 : 6a-6b 꼴에서 a, b에 적당한 자연수를 대입하면 된다.
- r=1~5 : 아래 식을 이용한다. 큰 양수를 표현하려면 n을 크게, 절댓값이 큰 음수를 표현하려면 a를 크게 하면 된다. 꼭 아래 식을 이용하지 않더라도 표현할 수 있다. 예를 들어 34의 경우 6으로 나눈 나머지가 4이지만 54-20과 같이 40(3n+1)-6a 꼴이 아닌 형태로 표현할 수 있다.
- r=1, 5 : 각각 (6n+1)X-6a, (6n+5)X-6a 꼴에서 a에 적당한 자연수를, n에 음이 아닌 적당한 정수를 대입한다.
- r=2, 3, 4 : 각각 20(3n+1)-6a, 945(2n+1)-6a, 40(3n+1)-6a 꼴에서 a, n에 적당한 자연수를 대입한다.
2.2. 약수의 개수가 n인 과잉수
약수의 개수가 n인 과잉수는 n의 값에 따라서 존재하지 않을 수도, 유한히 존재할 수도, 무수히 많이 존재할 수도 있다.
(여기서 a, b, c, d, e는 소수이고, a≠b, c>2, e>3이다.)
- 약수가 1개인 자연수는 1이고 1은 부족수이다. 또, 약수가 소수 개인 과잉수는 소인수가 하나뿐이므로 존재하지 않는다.
- 소인수가 하나뿐인 자연수는 an-1의 꼴로 나타내어지고, 진약수의 합은 1+a+a2+...+an-2
- 소인수가 하나뿐인 자연수는 an-1의 꼴로 나타내어지고, 진약수의 합은 1+a+a2+...+an-2
- 따라서 약수가 1, 2, 3, 5개인 과잉수는 존재하지 않고, 약수가 4개인 과잉수는 소인수분해 형식이 a3이거나 (같은 특정 소수 a의 세제곱) a×b의 꼴인데 (단, 두 소수 a와 b는 반드시 서로 달라야 한다) , a×b 꼴의 진약수의 합은 1+a+b이고, 1+a+b>ab에서 ab-a-b+1=(a-1)(b-1)<2이다. 이를 만족시키는 서로 다른 소수 a, b는 존재하지 않는다. 따라서 약수가 4개인 과잉수가 존재하지 않으므로, 약수가 5개 이하인 과잉수는 존재하지 않는다.
- 두 소수의 곱으로 나타나는 4 이상의 임의의 자연수 n에 대해, 약수의 개수가 n인 과잉수의 개수는 유한하다. 이들은 ac-1×bd-1의 꼴인데, 모두 짝수이다. d=2이면 a=2, b<2c-1이거나 a=3, b=2인 경우만 가능하다.
- 홀수일 때, a와 b를 각각 3, 5라 하고 c와 d를 아무리 크게 해도 약수의 합은 자신의 $$ \frac{15}{8} $$배보다 작으므로 과잉수가 아니다. 실제로 약수의 합을 구해 보면 $$ (1+3+3^2+...+3^{c-1})(1+5+5^2+...+5^{d-1}) < 3^{c-1} \times 5^{d-1} \times \frac{3}{2} \times \frac{5}{4}$$이다. 마찬가지로 3 이상의 소수 a, 5 이상의 소수 b에 대하여 약수의 합은 자신의 $$ \frac{ab}{(a-1)(b-1)} $$배보다 작으므로 역시 과잉수가 아니다.
- $$ d=2 $$일 때,
$$ a=2 $$일 경우 약수의 합은 $$ (b+1)(2^c-1) $$이며, 과잉수의 조건에 의해 $$ (b+1)(2^c-1)>b \times 2^c $$이다. 이를 정리하면 $$ b<2^c-1 $$이다.
$$ b=2 $$일 경우 약수의 합은 $$ \displaystyle 3 \times \frac{a^c-1}{a-1} $$이며, 과잉수의 조건에 의해 $$ \displaystyle 3 \times \frac{a^c-1}{a-1} >2 \times 2a^{c-1} $$이다. 이를 정리하면 $$ a^{c-1}(a-4)+3<0 $$이다. $$ a $$는 $$ 2 $$가 아닌 자연수이고 $$ c>2 $$이므로 $$ a=3 $$이다. - 이에 따라 약수의 개수가 c×d인 과잉수를 구해보면 다음과 같다.
- 3개 이상의 소수의 곱으로 나타나는 임의의 자연수 n에 대해, 약수의 개수가 n인 과잉수의 개수는 무한하다. 이는 6(=2×3)보다 큰 6의 배수는 모두 과잉수라는 점을 이용하여 다음과 같이 증명할 수 있다.
- 약수가 3개의 소수의 곱으로 나타나는 자연수는 소인수가 3개 이하이며, 처음 두 소인수를 2와 3으로 두고 소인수를 하나 더 쓰는 순간 과잉수가 된다. 예를 들어 약수가 12(=2×2×3)개인 자연수는 22×3×e, 2×32×e 또는 2×3×e2이다.
- 약수가 4개 이상의 소수 n개의 곱으로 나타나는 경우 그 중 (n-2)개를 하나로 묶어서 소인수가 3개인 것처럼 표현하고, 나머지 2개의 소인수를 2와 3이라고 하면 과잉수가 된다. 예를 들어 약수가 210(=2×3×5×7)개인 자연수의 경우 2와 3을 묶으면 210=6×5×7이므로 약수가 210개인 과잉수의 꼴로 e5×24×36을 들 수 있다.
2.3. 자연수 n과 서로소인 과잉수
임의의 자연수 n에 대해 n과 서로소인 과잉수는 무수히 많다. 다만 n을 적절히 잡는 순간 가장 작은 과잉수는 무시무시하게 커진다. 예를 들어 n = 2인 최소의 과잉수는 945이지만, n = 6[13]일 때는 5,391,411,025이고, n = 30[14]일 때는 20,169,691,981,106,018,776,756,331이며, n = 210일 때는 무려 49,061,132,957,714,428,902,152,118,459,264,865,645,885,092,682,687,973이다.
- 앞에서 언급한 6=2×3, 30=2×3×5, 210=2×3×5×7로, 가장 작은 소수부터 각각 2, 3, 4개의 소수를 곱한 수이다. 즉 1~p번째로 작은 소수 p개와 서로소인 과잉수의 최솟값은 p가 커짐에 따라 무시무시하게 커지는 것이다.
- 서로 다른 소수 p1, p2, ..., pk,의 곱 p1p2...pk의 약수의 합은 (1 + p1) × (1 + p2) × ... × (1 + pk)이며, 이는 p1p2...pk의 (1 + 1/p1) × (1 + 1/p2) × ... × (1 + 1/pk)배이다. 따라서 소인수가 p1, p2, ..., pk,인 임의의 자연수의 약수의 합은 그 자연수의 (1 + 1/p1) × (1 + 1/p2) × ... × (1 + 1/pk)배 이상이다. (1 + 1/p1) × (1 + 1/p2) × ... × (1 + 1/pk) ≥ 1 + 1/p1 + 1/p2 ... + 1/pk이고, 레온하르트 오일러가 증명한 소수의 역수의 합의 발산성에 의해 1 + 1/p1 + 1/p2 ... + 1/pk > 2를 만족하고, n의 소인수를 포함하지 않는 유한수열 {pk}이 항상 존재한다. 따라서 임의의 자연수 n에 대해 n과 서로소인 과잉수가 항상 존재하고, 과잉수가 존재하므로 그 개수는 무수히 많다. 자연수 n의 소인수를 p'1, p'2, ..., p'm이라 하면 p1 = p'm + 1, p2 = p'm + 2, ..., pk = p'm + k로 잡고, 소수의 개수가 무한하므로 이들의 역수의 합이 2를 넘도록 k를 충분히 크게 하면 된다.
- 예를 들어 n=2의 경우, n의 소인수는 2뿐이므로 이어지는 소수인 3, 5, 7, ...의 곱의 약수의 합 (3 + 1) × (5 + 1) × (7 + 1) ×...이 이들의 곱인 3 × 5 × 7 ×...의 2배를 초과하는 지점을 구하면 되는데, 그 지점은 이어지는 소수의 최댓값이 13인 지점이다(약수의 합=32256, 소수의 곱의 2배=30030). 따라서 3 × 5 × 7 × 11 × 13 = 15015는 홀수인 과잉수이다. 하지만 실제로는 그보다 훨씬 작은 홀수 과잉수 945가 존재한다.
2.4. 과잉수의 비율
1부터 n까지의 과잉수의 개수를 표로 정리하면 다음과 같다.
과잉수의 비율은 처음에 급격히 증가하다가 어느 순간 거의 늘어나지 않으면서 일정한 값에 수렴한다. 이 값은 0.2474 이상 0.2480 이하로 알려져 있다. 수가 커질 때 소인수가 많아지면서 과잉수의 비율도 크게 늘어날 것이라는 직관과 충돌하는 부분.
과잉수의 비율이 1/6 이하로 떨어지지 않음을 보이는 것은 쉬운데, 6을 제외한 6의 배수는 모두 과잉수임을 이용하면 된다. 실제로 n = 24에서 과잉수의 비율이 최초로 1/6 이상이 된 이후로, n = 40에서 비율이 1/6을 초과하면서 더이상 1/6 이하로 떨어지지 않는다.
과잉수의 비율은 n = 7254에서 최대가 되며, 이후 비율은 수렴값을 기준으로 불규칙하게 진동한다. 극대와 극소를 기준으로 과잉수의 개수를 다시 정리하면 다음과 같다.
3. 기타
- 100보다 작은 과잉수는 12, 18, 20, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70, 72, 78, 80, 84, 88, 90, 96의 21개다. 또 100도 과잉수이므로 100 이하의 과잉수는 22개다.
- 홀수인 과잉수를 작은 것부터 10개 나열하면 945, 1575, 2205, 2835, 3465, 4095[15], 4725, 5355, 5775[16], 5985이며, 945부터 5355까지는 공차가 630인 등차수열[17]을 이룬다. 홀수이면서 일의 자리가 5가 아니어서 5의 배수가 아닌, 다시 말해 10과 서로소인 최소의 과잉수는 81081(=34×7×11×13, 약수의 합은 162624)로, 175번째로 작은 홀수 과잉수이다. 더 많은 예시는 이 수열을 참조.
- 10n-1인 최초의 과잉수는 999999이며, 10과 서로소인 과잉수 중 26번째이다. (진약수의 합은 1042881)
- 모든 자리수가 1인 최초의 과잉수는 111,111,111,111,111,111(R18)이며 진약수의 합은 121,854,250,714,995,689이다.
[1] 자신을 제외한 모든 양의 약수[2] $$\sigma_1\left(n\right)$$은 $$n$$의 모든 약수들의 합. 즉, n의 모든 약수의 합에서 n을 빼므로, 진약수의 합이다.[3] 즉 2도 과잉수가 될 수 없다. 참고로 2의 경우에는 소수 중 유일한 짝수이며, 1은 소수에 해당되지 않는다.[4] 물론 홀수와 소수는 다른 개념이다.[5] 동시에 홀수의 첫 번째 반완전수이다.[6] 반완전수는 진약수의 합으로 표기될 수 있는 경우가 한두 가지 밖에 없는 것도 있지만, 대부분은 어떤 과잉수 자기자신과 동일하게 만드는 방법이 3가지 이상인 것도 많이 있다. 즉 괴짜수는 그러한 방법이 단 한 가지도 없는 과잉수이다.[7] 6n(n은 2이상의 자연수)은 반드시 진약수로 1, n, 2n, 3n을 가지므로 이들의 합만 해도 이미 1+n+2n+3n=6n+1>6n이다.[8] 원시 과잉수[9] 원시 반완전수[10] 후술하겠지만 977은 945+20+12로 나타낼 수 있다.[11] a=2이면 997[12] b=2이면 977[13] 홀수이면서 3의 배수가 아닌 수[14] 홀수이면서 3의 배수도 아니고 끝자리가 5가 아닌 수[15] 메르센 수 M(12)=212-1로, 메르센 수 중 첫 과잉수다.[16] 처음으로 9의 배수가 아닌 홀수 과잉수[17] 즉, 315를 제외한 5355 이하의 모든 홀수 과잉수는 315의 배수이다.