과잉수

1. 개요

2. 성질

• 소수는 (진약수가 1밖에 없으므로) 모두 부족수이고[3] 1 역시 부족수이므로[4] 과잉수는 모두 합성수이며, 소인수가 적어도 2개 이상, 약수가 적어도 6개 이상, 각 소인수의 지수의 합이 적어도 3 이어야 한다. 물론 역으로 합성수라고 해서 반드시 과잉수인 것은 아니다.[5]
• 가장 작은 과잉수는 12이며 가장 작은 홀수 과잉수는 945이다.[6]
• 과잉수 중 진약수의 일부의 합이 자기 자신과 같아지는 것은 반완전수이고[7], 진약수의 일부를 더해도 자기 자신을 나타낼 수 없으면 괴짜수이다.
• 자기 자신을 제외한 완전수, 과잉수의 배수는 모두 과잉수이다. 그러므로 과잉수는 무한히 많다. 예를 들어 완전수인 6의 경우, 6을 제외한 6의 배수는 모두 과잉수이다.[8] 마찬가지로 완전수를 진약수로 갖는 모든 자연수는 과잉수이다. 그리고 진약수들이 모두 부족수인 과잉수 즉 다른 과잉수 또는 완전수의 자기자신이 아닌 배수들로 표기될 수 없는 과잉수는 primitive abundant number[9]라고 하며, 1000 이하의 수 중 딱 14개 존재한다. [10]원시 과잉수 역시 무한히 많다. 또한, 완전수까지 포함한다면 총 17개가 있다. 이들 중 15개는 (반)완전수이고, 나머지 둘( 70, 836)은 괴짜수이다. 마찬가지로 어떤 반완전수의 진약수에 반완전수가 전혀 없어서 모두 부족수, 또는 괴짜수와 부족수이더라도 일부 진약수의 합이 자기자신이 되면 그 반완전수는 primitive semiperfect number[11]이다.
• 2ⁿ×p(단 p는 2ⁿ<p<2ⁿ⁺¹인 소수)인 경우 원시 과잉수 혹은 완전수가 되며, 특히 p=2ⁿ⁺¹-1인 경우 이 수는 완전수가 된다. 다만 이때 모든 짝수 완전수는 2ⁿ×p 형태를 가지지만 모든 원시 과잉수가 2ⁿ×p의 형태인 것은 아니다. 만약 p<2ⁿ이면 과잉수지만 해당 수를 2로 나눈 값[12] 또한 과잉수가 되어 원시 과잉수가 아니며, p>2ⁿ⁺¹인 경우 부족수가 된다.
• 완전수 또는 과잉수 n의 약수(총 k개)를 각각 n₁, n₂, ..., n_k라 하면 n은 완전수 또는 과잉수이므로 n₁+n₂+...+n_k≥2n이다. m이 자연수일 때, 이들 각각에 m을 곱한 m×n₁, m×n₂, ..., m×n_k는 mn의 약수이고 (m×n₁)+(m×n₂)+...+(m×n_k)=m×(n₁+n₂+...+n_k)≥2mn이다. m>1이면 이 외에 1도 약수이고, 1은 (m×n_a)(a는 1≤a≤k인 자연수) 꼴로 나타낼 수 없으므로 mn의 모든 약수의 합은 최소 2mn+1로 2mn보다 크다. 따라서 m>1이거나, 즉 완전수 또는 과잉수의 2배, 3배, ...이거나 n이 과잉수이면 mn은 과잉수이며, 완전수인 경우는 완전수의 1배인 경우뿐이다.

2.1. 과잉수의 합과 차로 표현되는 정수

• 20161보다 큰 모든 정수는 2개의 과잉수의 합으로 표현할 수 있다. 예를 들어 20163은 945+19218, 1575+18588, 2205+17958 등으로 나타낼 수 있다.
• 6을 제외한 6의 배수는 모두 과잉수이므로, 6으로 나눈 나머지 r에 따라 n보다 크면 항상 2개의 과잉수의 합으로 표현할 수 있는 n이 서로 다르다. 다른 과잉수인 20, 56 등도 마찬가지이다. 또, 992 이상의 자연수는 2개 이상의 과잉수의 합으로 표현할 수 있다.[13]
• r=0이면 6의 배수이므로, 6a+6b 꼴로 나타낼 수 있는 최소의 수인 24 이상이면 2개의 과잉수의 합으로 나타낼 수 있다.
• r=1이면 945+40=985는 2개의 과잉수의 합으로 표현되지만 991, 997 등은 그렇지 않다. 마찬가지로 r=5이면 945+20=965는 2개의 과잉수의 합으로 표현되지만 971은 그렇지 않다.[14] 따라서 r=1 또는 5인 경우 나머지 경우보다 n이 크다. 3개의 과잉수의 합으로는 r=1일 때 (945+40+6a 또는 945+20+20+6a)=997 이상[15], r=5일 때 945+20+6b=977 이상[16]이면 표현 가능하다.
• 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인 과잉수

• 약수가 1개인 자연수는 1이고 1은 부족수이다. 또, 약수가 소수 개인 과잉수는 소인수가 하나뿐이므로 존재하지 않는다.
• 소인수가 하나뿐인 자연수는 a^n-1의 꼴로 나타내어지고, 진약수의 합은 1+a+a²+...+a^n-2<a^n-1/(a-1)이므로 이러한 형태의 과잉수는 존재하지 않는다.
• 따라서 약수가 1, 2, 3, 5개인 과잉수는 존재하지 않고, 약수가 4개인 수는 소인수분해가 a³이거나 (특정 소수 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개 이하인 과잉수는 존재하지 않는다. 즉, 모든 과잉수는 최소한 약수의 개수가 6개 이상이다. 그리고 그뿐 아니라 소인수도 적어도 2개를 가진다.
• 두 소수의 곱으로 나타나는 4 이상의 임의의 자연수 n에 대해, 약수의 개수가 n인 과잉수의 개수는 유한하다. 이들은 a^c-1×b^d-1의 꼴인데, 모두 짝수이다. d=2이면 a=2, b<2^c-1이거나 a=3, b=2인 경우만 가능하다.
• 홀수일 때, a와 b를 각각 3, 5라 하고 3의 지수인 c와 5의 지수인 d의 값을 아무리 크게 해도 약수의 합은 자신의 [math( \frac{15}{8} )]배보다 작으므로 과잉수가 아니다. 실제로 약수의 합을 구해 보면 [math( (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})]이다. 마찬가지로 a가 3 이상의 소수이고, b가 5 이상의 소수일 때 약수의 합은 자신의 [math( \frac{ab}{(a-1)(b-1)} )]배보다 작으므로 역시 과잉수가 아니다.
• [math( d=2 )]일 때,
  [math( a=2 )]일 경우 약수의 합은 [math( (b+1)(2^c-1) )]이며, 과잉수의 조건에 의해 [math( (b+1)(2^c-1)>b \times 2^c )]이다. 이를 정리하면 [math( b<2^c-1 )]이다.
  [math( b=2 )]일 경우 약수의 합은 [math( \displaystyle 3 \times \frac{a^c-1}{a-1} )]이며, 과잉수의 조건에 의해 [math( \displaystyle 3 \times \frac{a^c-1}{a-1} >2 \times 2a^{c-1} )]이다. 이를 정리하면 [math( a^{c-1}(a-4)+3<0 )]이다. [math( a )]는 [math( 2 )]가 아닌 자연수이고 [math( c>2 )]이므로 [math( a=3 )]이다.
• 이에 따라 약수의 개수가 c×d인 과잉수를 구해보면 다음과 같다.



c×d

과잉수

개수




6

12, 18, 20

3




9

36, 100, 196

3




10

48, 80, 112, 162, 176, 208, 272, 304, 368, 464

10




14

192, 320, 448, 704, 832, 1088, 1216, 1458, …, 7232

30




15

144, 324, 400, 784, 1936, 2500, 2704, …, 15376

13




21

576, 1600, 2916, 3136, 7744, 10816, …, 1032256

31




22

3072, 5120, 7168, 11264, 13312, 17408, …, 2087936

309




25

1296, 10000, 38416, 234256, …, 14776336

11




26

12288, 20480, 28672, 45056, 53248, …, 33501184

1027

• 3개 이상의 소수의 곱으로 나타나는 임의의 자연수 n에 대해, 약수의 개수가 n인 과잉수의 개수는 무한하다. 이는 완전수인 6(=2×3)보다 큰 6의 배수는 모두 과잉수라는 점을 이용하여 다음과 같이 증명할 수 있다.
• 약수가 3개의 소수의 곱으로 나타나는 자연수는 소인수가 3개 이하이며, 처음 두 소인수를 2와 3으로 두고 소인수를 하나 더 쓰는 순간 과잉수가 된다. 예를 들어 약수가 12(=2×2×3)개인 자연수는 2²×3×e, 2×3²×e 또는 2×3×e²이다.
• 약수가 4개 이상의 소수 n개의 곱으로 나타나는 경우 그 중 (n-2)개를 하나로 묶어서 소인수가 3개인 것처럼 표현하고, 나머지 2개의 소인수를 2와 3이라고 하면 과잉수가 된다. 예를 들어 약수가 210(=2×3×5×7)개인 자연수의 경우 2와 3을 묶어서 표현하면 210=6×5×7이므로 약수가 210개인 과잉수의 꼴로 e⁵×2⁴×3⁶, e⁵×2⁶×3⁴, e⁴×2⁵×3⁶, e⁴×2⁶×3⁵, e⁶×2⁴×3⁵, e⁶×2⁵×3⁴을 들 수 있다.

2.3. 자연수 n과 서로소인 과잉수

• 앞에서 언급한 6=2×3, 30=2×3×5, 210=2×3×5×7로, 가장 작은 소수부터 각각 2, 3, 4개의 소수를 곱한 수이다. 즉 1~p번째로 작은 소수 p개와 서로소인 과잉수의 최솟값은 p가 커짐에 따라 무시무시하게 커지는 것이다.
• 서로 다른 소수 p₁, p₂, ..., p_k,의 곱 p₁p₂...p_k의 약수의 합은 (1 + p₁) × (1 + p₂) × ... × (1 + p_k)이며, 이는 p₁p₂...p_k의 (1 + 1/p₁) × (1 + 1/p₂) × ... × (1 + 1/p_k)배이다. 따라서 소인수가 p₁, p₂, ..., p_k,인 임의의 자연수의 약수의 합은 그 자연수의 (1 + 1/p₁) × (1 + 1/p₂) × ... × (1 + 1/p_k)배 이상이다. (1 + 1/p₁) × (1 + 1/p₂) × ... × (1 + 1/p_k) ≥ 1 + 1/p₁ + 1/p₂ ... + 1/p_k이고, 레온하르트 오일러가 증명한 소수의 역수의 합의 발산성에 의해 1 + 1/p₁ + 1/p₂ ... + 1/p_k > 2를 만족하고, n의 소인수를 포함하지 않는 유한수열 {p_k}이 항상 존재한다. 따라서 임의의 자연수 n에 대해 n과 서로소인 과잉수가 항상 존재하고, 과잉수가 존재하므로 그 개수는 무수히 많다. 자연수 n의 소인수를 p'₁, p'₂, ..., p'_m이라 하면 p₁ = p'_{m + 1}, p₂ = p'_{m + 2}, ..., p_k = 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. 과잉수의 비율

3. 기타

• 100보다 작은 과잉수는 총 21개다. 또 100도 과잉수이므로 100 이하의 과잉수는 22개다.
• 10ⁿ-1인 최초의 과잉수는 999999이며, 10과 서로소인 과잉수 중 26번째이다. (진약수의 합은 1,042,881)
• 모든 자리수가 1인 최초의 과잉수는 111,111,111,111,111,111(R₁₈)이며 진약수의 합은 121,854,250,714,995,689이다.
• 소인수를 기준으로 살펴보면 아래와 같다. 그외의 다른 특정 소인수가 없는 경우도 추후 조사 후 추가 예정.
• 소인수에 2가 없는, 즉 홀수인 과잉수를 작은 것부터 10개 나열하면 945, 1575, 2205, 2835, 3465, 4095[19], 4725, 5355, 5775, 5985이며, 945부터 5355까지는 공차가 630인 등차수열을 이룬다. 즉, 5355 이하의 모든 홀수 과잉수는 315의 배수이다.
• 소인수에 2, 3이 없는 가장 작은 과잉수는 5391411025이다. 과잉수에서 2, 3이 차지하는 비중이 매우 크다는 것을 알 수 있다.
• 소인수에 2, 5가 없는 가장 작은 과잉수는 81081(=3⁴×7×11×13, 약수의 합은 162624)이다. 더 많은 예시는 이 수열을 참조.
• 소인수에 2, 7이 없는 가장 작은 과잉수는 6435(=3²×5×11×13, 약수의 합은 13104)이다. 그리고 5985에 이어 11번째 홀수 과잉수이다.
• 소인수에 2가 없고 9의 배수가 아닌 가장 작은 과잉수는 5775이다.
• 소인수에 3, 5가 없는 가장 작은 과잉수는 56이다.
• 소인수에 3, 5, 7이 없는 가장 작은 과잉수는 88이다.
• 소인수에 2, 7, 11이 없는 가장 작은 과잉수는 29835(=3³×5×13×17, 약수의 합은 60480)이다.
• 소인수에 2, 7, 13이 없는 가장 작은 과잉수는 7425(=3³×5²×11, 약수의 합은 14880)이다.

3.1. 1000 이하의 과잉수 목록

• 원시 과잉수는 ◎표시.
• 괴짜수는 ★표시.

• 1~99: 12, 18, 20◎, 24, 30, 36, 40, 42, 48, 54, 56, 60, 66, 70◎★, 72, 78, 80, 84, 88◎, 90, 96
• 100~199: 100, 102, 104◎, 108, 112, 114, 120, 126, 132, 138, 140, 144, 150, 156, 160, 162, 168, 174, 176, 180, 186, 192, 196, 198
• 200~299: 200, 204, 208, 210, 216, 220, 222, 224, 228, 234, 240, 246, 252, 258, 260, 264, 270, 272◎, 276, 280, 282, 288, 294
• 300~399: 300, 304◎, 306, 308, 312, 318, 320, 324, 330, 336, 340, 342, 348, 350, 352, 354, 360, 364, 366, 368◎, 372, 378, 380, 384, 390, 392, 396
• 400~499: 400, 402, 408, 414, 416, 420, 426, 432, 438, 440, 444, 448, 450, 456, 460, 462, 464◎, 468, 474, 476, 480, 486, 490, 492, 498
• 500~599: 500, 504, 510, 516, 520, 522, 528, 532, 534, 540, 544, 546, 550◎, 552, 558, 560, 564, 570, 572◎, 576, 580, 582, 588, 594
• 600~699: 600, 606, 608, 612, 616, 618, 620, 624, 630, 636, 640, 642, 644, 648, 650◎, 654, 660, 666, 672, 678, 680, 684, 690, 696
• 700~799: 700, 702, 704, 708, 714, 720, 726, 728, 732, 736, 738, 740, 744, 748◎, 750, 756, 760, 762, 768, 770, 774, 780, 784, 786, 792, 798
• 800~899: 800, 804, 810, 812, 816, 820, 822, 828, 832, 834, 836◎★, 840, 846, 852, 858, 860, 864, 868, 870, 876, 880, 882, 888, 894, 896
• 900~1000: 900, 906, 910, 912, 918, 920, 924, 928, 930, 936, 940, 942, 945◎, 948, 952, 954, 960, 966, 968, 972, 978, 980, 984, 990, 992, 996, 1000