|
정수론 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. 개요
不 可 觸 數 / untouchable number헝가리의 수학자 에르되시 팔이 창시한 개념이다. 어떤 자연수 n의 진약수를 모두 더한 수를 m이라고 하자. 이때 n 자리에 그 어떤 자연수를 넣더라도 m의 자리에 나타날 수 없는 수가 있는데, 이런 수를 불가촉 수라 한다. 한마디로 어떤 수의 모든 진약수들의 합이 될 수 없는 수를 불가촉 수라고 한다.
예컨대 2가 불가촉 수라는 것은, 이 세상에 존재하는 자연수 가운데 진약수의 총합으로 2를 가지는 수가 존재하지 않는다는 이야기이다.
불가촉이라는 용어는 untouchable의 번역어로, 불가촉천민 할 때의 그 불가촉이 맞다. 물론 그런 부정적인 의미로 쓰인 건 아니고, 어떤 수의 진약수들을 다 더해도 그 수에 닿을 수 없다는 뜻이다.
2. 예시
불가촉 수 중 가장 작은 10개를 나열하면 다음과 같다.더 많은 예시는 여기 참조.
1은 모든 소수들 중 하나의 진약수의 합으로 나타낼 수 있고(그야 당연히 소수의 진약수는 1밖에 없으니까) 3은 4의 진약수 합으로(1+2), 4는 9의 진약수 합으로(1+3) 나타낼 수 있기 때문에 불가촉 수가 아니다.
2는 1을 포함한 자연수의 합으로 나타내려면 1+1밖에 없어서 중복되지 않는 자연수의 합으로 나타내는 게 불가능하고 5는 1을 포함한 중복되지 않는 자연수의 합으로 나타내려면 1+4밖에 없는데 4의 배수면서 2의 배수가 아닌 수는 없기 때문에 불가능하다. 따라서 2와 5는 불가촉 수가 된다.
아래 표는 n의 진약수의 합이 m이라 했을 때 그 예시들. 단, 진약수의 합에 해당하는 게 2가지 이상일 경우 어떤 수가 다른 정수의 진약수의 합으로 표현 되는 것 중 가장 작은 수로 표기함. 이 말은 진약수의 총합이 서로 같은 자연수가 두 개 이상 있을 수도 있다는 말이다. 이러한 두 쌍의 수를 '친구수'라고 한다. 친화수와 이름이 비슷하기 때문에 혼동하지 않도록 주의해야 한다.[1]
| m | n | 비고 |
| 0 | 1 (진약수 없음) | |
| 1 | 모든 소수 (1) | 기초수 |
| <rowcolor=#111111> 2 | 불가촉 수 | |
| 3 | 4 (1+2) | |
| 4 | 9 (1+3) | |
| <rowcolor=#111111> 5 | 불가촉 수 | 홀수 불가촉 수 |
| 6 | 6 (1+2+3) | 완전수 |
| 7 | 8 (1+2+4) | |
| 8 | 10 (1+2+5) | |
| 9 | 15 (1+3+5) | |
| 10 | 14 (1+2+7) |
3. 골드바흐 수와의 연관성 및 성질
어떤 자연수 x가 y의 진약수의 합으로 나타내어진다고 할 때, x의 값에 따라서 가능한 y의 개수를 n개라고 할 때, n가지 방법으로 표현 가능한 가장 작은 수들은 다음과 같다. 추가 정보는 골드바흐 추측 문서를 참고할 것.- 1가지 : 3=1+2(4의 진약수)
- 2가지 : 6=1+2+3(6의 진약수)=1+5(25의 진약수)
- 3가지 : 21=1+2+3+6+9(18의 진약수)=1+3+17(51의 진약수)=1+7+13(91의 진약수)
- 4가지 : 37=1+5+31(155의 진약수)=1+7+29(203의 진약수)=1+13+23(299의 진약수)=1+17+19(323의 진약수)
- 5가지 : 31=1+2+4+8+16(32의 진약수)=1+5+25(125의 진약수)=1+7+23(161의 진약수)=1+11+19(209의 진약수)=1+13+17(221의 진약수)
- 6가지 : 49=1+3+5+15+25(75의 진약수)=1+5+43(215의 진약수)=1+7+41(287의 진약수)=1+11+37(407의 진약수)=1+17+31(527의 진약수)=1+19+29(551의 진약수)
- 7가지 : 79=1+5+73(365의 진약수)=1+7+71(497의 진약수)=1+11+67(737의 진약수)=1+17+61(1037의 진약수)=1+19+59(1121의 진약수)=1+31+47(1457의 진약수)=1+37+41(1517의 진약수)
- 8가지 : 73=1+2+7+14+49(98의 진약수)=1+5+7+25+35(175의 진약수)=1+5+67(335의 진약수)=1+11+61(671의 진약수)=1+13+59(767의 진약수)=1+19+53(1007의 진약수)=1+29+43(1247의 진약수)=1+31+41(1271의 진약수)
- 9가지 : 91=1+7+83(581의 진약수)=1+11+79(869의 진약수)=1+17+73(1241의 진약수)=1+19+71(1349의 진약수)=1+23+67(1541의 진약수)=1+29+61(1769의 진약수)=1+31+59(1829의 진약수)=1+37+53(1961의 진약수)=1+43+47(2021의 진약수)
완전수는 불가촉 수가 될 수 없다. 완전수의 정의가 진약수를 모두 더하면 자기 자신이 되는 수기 때문에 당연하다. 친화수와 사교수 역시 같은 이유로 불가촉 수가 될 수 없다. 즉, {불가촉 수} ∩ ({완전수} ∪ {친화수} ∪ {사교수}) = Ø
단, 반완전수나 부족수 중에서는 불가촉 수가 있을 수 있다. 예를 들어 불가촉 수 중 하나인 96의 진약수는 {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48}인데 그 중에서 {16, 32, 48}만 더하면 96이 된다.
불가촉 수는 일단 현재까지 발견된 수로 한정한다면 5가 유일하게 홀수이고 나머지는 모두 짝수이다. 그러나 5가 유일한 홀수 불가촉 수가 맞는지, 아니면 5 이외의 홀수 불가촉 수가 더 있는지는 아직 알려져 있지 않다. 아래의 증명 참고.
n이 2 이상의 자연수일 때, 2n-1은 불가촉 수가 될 수 없으며, 2n의 진약수의 합으로 2n-1이 된다. 아래는 그 예시.
| n | 2n-1 | 2n | 2n의 진약수의 합 |
| 1 | 1 | 2 | 1=1 |
| 2 | 3 | 4 | 1+2=3 |
| 3 | 7 | 8 | 1+2+4=7 |
| 4 | 15 | 16 | 1+2+4+8=15 |
| 5 | 31 | 32 | 1+2+4+8+16=31 |
| 6 | 63 | 64 | 1+2+4+8+16+32=63 |
같은 이유로 첫 항이 1이고 이웃한 두 항의 공비가 소수인 등비수열의 합, 즉, 특정 소수의 0제곱부터 n제곱까지의 합 역시 불가촉 수가 될 수 없다.(단, n은 자연수) [2]
| n | 3n | 3n의 진약수의 합 = 30+...+3n-1 | 5n | 5n의 진약수의 합 = 50+...+5n-1 |
| 1 | 3 | 1=1 | 5 | 1=1 |
| 2 | 9 | 4=1+3 | 25 | 6=1+5 |
| 3 | 27 | 13=1+3+9 | 125 | 31=1+5+25 |
| 4 | 81 | 40=1+3+9+27 | 625 | 156=1+5+25+125 |
| 5 | 243 | 121=1+3+9+27+81 | 3125 | 781=1+5+25+125+625 |
| 6 | 729 | 364=1+3+9+27+81+243 | 15625 | 3906=1+5+25+125+625+3125 |
| n | 7n | 7n의 진약수의 합 = 70+...+7n-1 | 11n | 11n의 진약수의 합 = 110+...+11n-1 |
| 1 | 7 | 1=1 | 11 | 1=1 |
| 2 | 49 | 8=1+7 | 121 | 12=1+11 |
| 3 | 343 | 57=1+7+49 | 1331 | 133=1+11+121 |
| 4 | 2401 | 400=1+7+49+343 | 14641 | 1464=1+11+121+1331 |
4. 증명
5가 유일한 홀수 불가촉 수가 맞는지의 여부는 아직 증명되지 않았으나 골드바흐 추측이 참인 것으로 증명된다면 자동으로 증명된다. 그 이유를 보자면,- 일단 홀수 21이 있다고 하자. 여기서 1을 빼 보면 20이 된다.
- 골드바흐의 추측에 의거하여 위의 20을 두 소수의 합으로 나타내 보면 13+7 또는 17+3이 된다.
- 어떤 소수 a와 b가 있고(단, a와 b는 서로 다른 소수이다) 이 두 수를 곱한 수가 c라고 한다면, c의 진약수는 1, a, b 이렇게 3개가 된다.
- 이에 의거하여 계산해 보면, 13에서 7을 곱하면 91이 되는데 91의 진약수는 1, 7, 13 이렇게 3개이고 이를 모두 더하면 21이 된다. 이로써 21은 불가촉 수가 아니게 된다.
- 17×3의 경우도 마찬가지로 17×3 하면 51이 되고 51의 진약수는 1, 3, 17. 모두 더하면 21이 된다.
골드바흐의 추측에 의해 어떤 홀수가 불가촉 수가 아님을 증명하는 예를 몇 가지 들자면,
| n | n-1 | a+b | a×b | a×b의 진약수의 합 |
| 9 | 8 | 3+5 | 3×5=15 | 1+3+5=9 |
| 11 | 10 | 3+7 | 3×7=21 | 1+3+7=11 |
| 13 | 12 | 5+7 | 5×7=35 | 1+5+7=13 |
| 15 | 14 | 3+11 | 3×11=33 | 1+3+11=15 |
| 17 | 16 |
3+13 5+11 |
3×13=39 5×11=55 |
1+3+13=17 1+5+11=17 |
| 19 | 18 |
5+13 7+11 |
5×13=65 7×11=77 |
1+5+13=19 1+7+11=19 |
만약에 5가 유일한 홀수 불가촉 수라는 사실이 증명된다면, 2와 5를 제외한 모든 불가촉 수가 합성수라는 사실 또한 자동으로 증명된다.
불가촉 수가 무한히 존재한다는 사실은 이미 증명이 되어 있다. 증명한 사람은 바로 불가촉 수의 개념을 창시한 에르되시 팔.
[1]
예를 들어 16와 33은 진약수의 합이 15로 서로 동일하므로 친구수에 해당이 된다. 마찬가지로 12와 26도 진약수를 모두 더한 결과가 16으로 서로 같기 때문에 친구수이다. 그리고 친구수의 서로 같은 진약수의 합이 얼마린지도 나타내면 된다. 또한 진약수의 합이 서로 같은 셋 이상의 자연수의 쌍은 '우애수'라고 한다.
[2]
이런 수는 p가 소수일 때 p진법으로 나타내면 1이 n개 늘어선 수로, pn의 진약수의 합이 된다. 그리고 그 수에 (p-1)을 곱하면 pn-1이 된다. 그리고 이 수는 p진법에서 (p^n-1)/(p-1)의 꼴로 (단, p는 소수, n은 자연수) 나타낼 수 있다.
[3]
예시로, 45의 진약수의 합은 33이고, 75는 진약수의 합이 49이며, 99는 57이 진약수의 합이며, 135는 105가 진약수의 합이며, 117은 75, 147과 153은 81, 171은 89, 189는 131 인데, 모두 소수의 거듭제곱이 아니면서 약수가 6개인 진약수의 합이 홀수인 홀수이다. 또한 50의 진약수의 합은 43, 98의 진약수의 합은 73, 36은 55, 72는 123, 100은 117인 것처럼 약수가 6개 이상이고 2의 거듭제곱이 아인 짝수 중에서도 진약수의 합이 홀수가 되는 수가 있으며, 이련 경우는 모두 제곱수와 2의 곱이거나 짝수의 제곱수다.