최근 수정 시각 : 2022-04-06 11:16:12

과잉수

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

약수의 합에 따른 자연수의 분류
자기 자신과의 비교 과잉수 완전수 부족수
일부의 합 사슬 주기 1 주기 2 주기 3 이상
진약수의 합 완전수 <colbgcolor=#fff,#1f2023> 친화수 <colbgcolor=#ddd,#333> 사교수
비자명 진약수의 합 <colbgcolor=#000> 준완전수 혼약수 준사교수
진약수의 합의 약수 초완전수 ? ?
기타 반완전수 괴짜수 불가촉 수



1. 개요2. 성질
2.1. 과잉수의 합과 차로 표현되는 정수2.2. 약수의 개수가 n인 과잉수2.3. 자연수 n과 서로소인 과잉수2.4. 과잉수의 비율
3. 기타
3.1. 1000 이하의 과잉수 목록

1. 개요

, abundant number

자연수 [math(n)]에 대하여, [math(n)]의 모든 진약수[1]들의 합이 [math(n)]보다 크면 [math(n)]을 과잉수라고 한다. 즉, 약수의 합이 [math(2n)]보다 크면 과잉수인 것이다. 약수 함수(divisor function)를 이용해 나타내면 다음을 만족하는 자연수 [math(n)]을 말한다.

[math(n<\sigma_1\left(n\right)-n)][2]

또는 이 식을 변형하여 다음과 같이 나타낼 수 있다.

[math(2n<\sigma_1\left(n\right))]

2. 성질

  • 소수는 (진약수가 1밖에 없으므로) 모두 부족수이고[3] 1도 (그야 당연히 진약수가 없으니까) 부족수이므로 과잉수는 모두 합성수이며, 소인수가 적어도 2개 이상, 약수가 적어도 6개 이상, 각 소인수의 지수의 합이 적어도 3 이어야 한다. 물론 역으로 합성수라고 해서 반드시 과잉수인 것은 아니다.
  • 가장 작은 과잉수는 12이며 가장 작은 홀수 과잉수는 945이다.[4]
  • 과잉수 중 진약수의 일부의 합이 자기자신과 같아지는 것은 반완전수이고[5], 진약수의 일부를 더해도 자기자신을 나타낼 수 없으면 괴짜수이다.
  • 자기 자신을 제외한 완전수, 과잉수의 배수는 모두 과잉수이다. 그러므로 과잉수는 무한히 많다. 예를 들어 완전수인 6의 경우, 6을 제외한 6의 배수는 모두 과잉수이다.[6] 마찬가지로 완전수를 진약수로 갖는 모든 자연수는 과잉수이다. 그리고 진약수들이 모두 부족수인 과잉수 즉 다른 과잉수 또는 완전수의 자기자신이 아닌 배수들로 표기될 수 없는 과잉수는 primitive abundant number[7]라고 하며, 1000 이하의 수 중 딱 14개 존재한다. 원시 과잉수 역시 무한히 많다. 또한, 완전수까지 포함한다면 총 17개가 있다. 이들 중 15개는 (반)완전수이고, 나머지 둘( 70, 836)은 괴짜수이다. 마찬가지로 어떤 반완전수의 진약수에 반완전수가 전혀 없어서 모두 부족수, 또는 괴짜수와 부족수이더라도 일부 진약수의 합이 자기자신이 되면 그 반완전수는 primitive semiperfect number[8]이다.
    • 2n×p(단 p는 2n<p<2n+1인 소수)인 경우 원시 과잉수 혹은 완전수가 되며, 특히 p=2n+1-1인 경우 이 수는 완전수가 된다. 다만 이때 모든 짝수 완전수는 2n×p 형태를 가지지만 모든 원시 과잉수가 2n×p의 형태인 것은 아니다. 만약 p<2n이면 과잉수지만 해당 수를 2로 나눈 값[9] 또한 과잉수가 되어 원시 과잉수가 아니며, p>2n+1인 경우 부족수가 된다.
    • 완전수 또는 과잉수 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/(a-1)이므로 이러한 형태의 과잉수는 존재하지 않는다.
  • 따라서 약수가 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개 이하인 과잉수는 존재하지 않는다. 즉, 모든 과잉수는 최소한 약수의 개수가 6개 이상이다. 그리고 그뿐 아니라 소인수도 적어도 2개를 가진다.
  • 두 소수의 곱으로 나타나는 4 이상의 임의의 자연수 n에 대해, 약수의 개수가 n인 과잉수의 개수는 유한하다. 이들은 ac-1×bd-1의 꼴인데, 모두 짝수이다. d=2이면 a=2, b<2c-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)개인 자연수는 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, e5×26×34, e4×25×36, e4×26×35, e6×24×35, e6×25×34을 들 수 있다.

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까지의 과잉수의 개수를 표로 정리하면 다음과 같다.
n 과잉수의 개수 비율
100 22 22%
200 46 23%
500 121 24.2%
1,000 246 24.6%
2,000 493 24.65%
5,000 1,239 24.78%
10,000 2,488 24.88%
20,000 4,953 24.77%
50,000 12,394 24.79%
100,000 24,795 24.80%
200,000 49,481 24.74%
500,000 123,779 24.756%
1,000,000 247,545 24.755%
2,000,000 495,036 24.752%
5,000,000 1,238,015 24.760%
10,000,000 2,476,737 24.767%
20,000,000 4,953,984 24.770%
50,000,000 12,382,841 24.766%
100,000,000 24,760,668 24.761%

과잉수의 비율은 처음에 급격히 증가하다가 어느 순간 거의 늘어나지 않으면서 일정한 값에 수렴한다. 이 값은 0.2474 이상 0.2480 이하로 알려져 있다. 수가 커질 때 소인수가 많아지면서 과잉수의 비율도 늘어나려다가 갑자기 줄어들기도 할 것이라는 직관과 충돌하는 부분이라고 생각할 수도 있으나 그렇진 않다.

과잉수의 비율이 1/6 이하로 떨어지지 않음을 보이는 것은 쉬운데, 완전수인 6을 제외한 6의 배수는 모두 과잉수임을 이용하면 된다. 실제로 n = 24에서 과잉수의 비율이 최초로 1/6 이상이 된 이후로, n = 40에서 비율이 1/6을 초과하면서 더이상 1/6 이하로 떨어지지 않는다.

과잉수의 비율은 n = 7254에서 최대가 되며, 이후 비율은 수렴값을 기준으로 불규칙하게 진동한다. 극대와 극소를 기준으로 과잉수의 개수를 다시 정리하면 다음과 같다.
n 과잉수의 개수 비율
7,254 1,810 24.952%
222,065 54,927 24.735%
16,880,388 4,181,307 24.770%
159,583,505 39,512,681 24.760%

3. 기타

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

3.1. 1000 이하의 과잉수 목록

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



[1] 자신을 제외한 모든 양의 약수 [2] [math(\sigma_1\left(n\right))]은 [math(n)]의 모든 약수들의 합. 즉, n의 모든 약수의 합에서 n을 빼므로, 진약수의 합이다. [3] 즉 2도 과잉수가 될 수 없다. 참고로 2의 경우에는 소수 중 유일한 짝수이며, 1은 소수에 해당되지 않는다. [4] 동시에 홀수의 첫 번째 반완전수이다. [5] 반완전수는 진약수의 합으로 표기될 수 있는 경우가 한두 가지 밖에 없는 것도 있지만, 대부분은 어떤 과잉수 자기자신과 동일하게 만드는 방법이 3가지 이상인 것도 많이 있다. 즉 괴짜수는 그러한 방법이 단 한 가지도 없는 과잉수이다. [6] 6n(n은 2이상의 자연수)은 반드시 진약수로 1, 2, 3, 6, n, 2n, 3n을 가지므로 이들의 합만 해도 이미 1+2+3+6+n+2n+3n=6n+12>6n이다. [7] 원시 과잉수 [8] 원시 반완전수 [9] 2n-1×p [10] 후술하겠지만 977은 945+20+12로 나타낼 수 있다. [11] a=2이면 997 [12] b=2이면 977 [13] 홀수이면서 3의 배수가 아닌 수 [14] 홀수이면서 3의 배수도 아니고 끝자리가 5가 아닌 수 [15] 메르센 수 M(12)=212-1로, 메르센 수 중 첫 과잉수다.