소수 (수론)

1=소수 (기수법) 좌측은 소수, 우측은 합성수. ...소수란 1보다 큰 자연수 중 1과 자기 자신만을 [[약수로 가지는 수다.]] 정수론에서 **소수**(素數, 발음: [소쑤], 씨수, 프라임 넘버)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수다. 그러나 6은 자신보다 작은 두 숫자의 곱(2×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수나 비소수라고 한다. 산술의 기본 정리의 '1보다 큰 모든 자연수는 그 자체가 소수이거나, 순서를 무시하고 유일한 소인수의 조합을 갖는다'는 내용을 바탕으로 정수론에서는 매우 중요한 주제로 다루어진다. 또한 현대에는 암호 분야에서의 기술적 사용으로 그 중요성이 부각되고 있다. 소수의 개수는 무한하며, 이는 유클리드의 정리에 의하여 최초로 논증되었다. 소수와 합성수를 구분해낼 수 있는 명확한 공식은 지금까지도 밝혀지지 않은 상태이나, 대역적으로 자연수 중 소수의 비율의 근사치를 예측하는 모델로는 여러가지가 알려져 있다. 이러한 방향으로의 연구의 첫 결과는 19세기 말에 증명된 소수 정리인데, 이는 무작위로 선택된 한 수가 소수일 확률은 그 수의 자릿수, 곧 로그값에 반비례함을 알려준다.
# 소수 목록
소수 목록 1000보다 작은 소수는 다음과 같다. A000040 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, … 여기서, 2는 유일한 짝수 소수이며, 2와 5를 제외한 모든 소수의 일의 자리 수는 1, 3, 7, 9 중 하나다. 10 미만의 소수는 4개이고, 100 미만의 소수는 25개, 1000 미만의 소수는 168개이며, 10000 미만의 소수는 1229개임이 밝혀져 있다.
# 소인수 분해
소인수 분해 정수론의 기본 정리에 의해, 모든 자연수는 꼭 한가지 방법으로 소수의 곱으로 표현할 수 있고 이를 소인수 분해의 일의성이라고 한다. 즉, 곱셈의 관점에서 소수는 자연수를 이루는 성분이다. 예를 들면, :23244 = 2^2 \times 3 \times 13 \times 149 이고 23244는 (약수의 순서를 무시하면) 단 한 가지 방법으로 소인수분해된다. 이 정리의 중요성은 소수들의 집합에서 1을 제외하는 이유 중의 하나다. 만일 1이 소수라면 이 정리의 엄밀한 진술을 위해 추가적인 제한조건을 필요로 하기 때문이다.
# 소수의 개수
소수는 무한하다. 이 명제를 유클리드의 정리라고 하며 가장 오래된 증명은 그리스 수학자 유클리드의 《유클리드 원론》(제9권, 정리 20)에서 볼 수 있다. 유클리드의 증명은 “어느 주어진 유한한 소수들 보다 더 많다.”라는 결론으로 표현되고, 그의 증명은 본래 아래와 같다. 유한 개의 소수가 존재한다고 가정하자. 이 유한 개의 소수들을 모두 곱한 값에 1을 더한다. (유클리드 수 참조) 그 결과값은 다른 어떤 소수로 나누어도 나머지가 1이므로 어떤 소수로도 나누어떨어지지 않는 수가 된다. 따라서 이 수가 소수라면 기존의 최대소수보다 큰 소수가 있다는 것이 증명되고, 이 수가 소수가 아니라고 해도 또다른 소수가 있어야 한다는 것을 의미하기 때문에 소수가 유한하다는 애초 가정에 모순이 존재함을 알 수 있다. 다른 수학자들도 각자의 증명을 내놓았다. 그 중 대카르트에 의한 증명은 모든 소수들의 역수의 합이 발산한다는 증명으로부터 소수의 개수가 무한함을 보였다.
# 역사
소수에 대한 최초의 기록은 고대 이집트 파피루스에서 찾을 수 있다. 파피루스에는 소수와 합성수를 구분해서 다른 형태로 표기되어 있었다. 그러나 소수에 대한 본격적인 연구는 고대 그리스에서 본격적으로 시작되었다. 《유클리드 원론》(기원전 300년경)에는 소수가 무한히 많다는 내용과 정수론의 기본 정리가 포함되어 있다. 유클리드는 메르센 소수로부터 완전수를 만드는 방법도 설명하였다. 그리고 고대 그리스의 수학자 에라토스테네스는 소수를 찾는 방법인 "에라토스테네스의 체" 를 개발했다. 유클리드 이후 17세기까지 소수에 대한 연구는 별로 없었다. 그러나 페르마는 1640년에 페르마 소정리를 증명 없이 발표하였다. 그 이후 근대에 리만 가설, 골트바흐 추측 등 여러 탐구가 이뤄졌다.
# 소수 찾기
현재까지 알려진 가장 간단한 방법으로 에라토스테네스의 체가 있다. 방법은 다음과 같다. # 찾고자 하는 범위의 자연수를 나열한다. #1은 지운다. # 2부터 시작하여, 2의 배수를 지워나간다. # 다음 소수의 배수를 모두 지운다. 이를 반복하여 마지막까지 지우면, 남는 수들이 소수가 된다. 이 과정은 사실 어떤 자연수 n이 소수임을 판정하기 위해서 \lfloor\sqrt{n}\rfloor까지만 진행하면 되는데여기서 어떤 실수 x에 대해, \lfloor x \rfloor는 x보다 작거나 같은 수들 중 가장 큰 정수를 뜻한다. 이를 바닥 함수라 한다., 수가 수를 나누기 위해서는 그 몫이 항상 필요하며 나누는 수와 몫 중 어느 하나는 반드시 \sqrt{n} 이하이기 때문이다. 아래 표로 이 방법을 활용하면 다음과 같이 된다.(4, 6, 8, 10은 제외(무조건 합성수기에넣어봤자 의미가 없다는 뜻이다.)) {| |+소수 표 |~~1~~ 소수도, 합성수도 아님 |2 |3 |5 |7 |~~9~~ 3으로 인해 합성수 판결. |- |11 |~~12~~ 2로 인해 합성수 판결 |13 |~~15~~ 3으로 인해 합성수 판결. |17 |19 |- |~~21~~ 3으로 인해 합성수 판결. |~~22~~ 2로 인해 합성수 판결 |23 |~~25~~ 5로 인해 합성수 판결 |~~27~~ 3으로 인해 합성수 판결. |29 |- |31 |~~32~~ 2로 인해 합성수 판결 |~~33~~ 3으로 인해 합성수 판결. |~~35~~ 5로 인해 합성수 판결 |37 |~~39~~ 3으로 인해 합성수 판결. |- |41 |~~42~~ 2로 인해 합성수 판결 |43 |~~45~~ 3으로 인해 합성수 판결. |47 |~~49~~ 7로 인해 합성수 판결 |- |~~51~~ 3으로 인해 합성수 판결. |~~52~~ 2로 인해 합성수 판결 |53 |~~55~~ 5로 인해 합성수 판결 |~~57~~ 3으로 인해 합성수 판결. |59 |- |61 |~~62~~ 2로 인해 합성수 판결 |~~63~~ 3으로 인해 합성수 판결. |~~65~~ 5로 인해 합성수 판결 |67 |~~69~~ 3으로 인해 합성수 판결. |- |71 |~~72~~ 2로 인해 합성수 판결 |73 |~~75~~ 3으로 인해 합성수 판결. |~~77~~ 7로 인해 합성수 판결 |79 |- |~~81~~ 3으로 인해 합성수 판결. |~~82~~ 2로 인해 합성수 판결 |83 |~~85~~ 5로 인해 합성수 판결 |~~87~~ 3으로 인해 합성수 판결. |89 |- |~~91~~ 7로 인해 합성수 판결 |~~92~~ 2로 인해 합성수 판결 |~~93~~ 3으로 인해 합성수 판결. |~~95~~ 5로 인해 합성수 판결 |97 |~~99~~ 3으로 인해 합성수 판결. |} 소수를 골라내기 위한 방법은 다음과 같다. 이 방법을 이용해 소수를 어느 정도 골라낼 수 있다. # 2와 5를 제외하면, 모든 소수의 일의 자리 수는 1, 3, 7, 9다. # 어떤 자연수 n이 소수임을 판정하기 위해선 \sqrt{n}까지의 수 중 1을 제외하고 그 자연수의 약수가 있는지 확인하면 된다. # 배수의 성질을 이용하면 쉽게 구할 수도 있다. 그 외에도 다양하고 복잡한 판정법이 존재하지만, 위의 세 가지는 당연하고 간단한 것들이다.
# 소수의 종류 및 관련 성질
모든 소수를 분류해서 해당 집합에 넣는 것은 아니지만, 일반적으로 알려진 특수한 소수에는 다음이 있다. * **가우스 소수** (Gaussian prime) : 가우스 정수 중 가우스 정수의 곱으로 나타낼 수 없는 수를 의미한다. * **메르센 소수** (Mersenne prime) : 2의 거듭제곱보다 1 작은 자연수(2^n - 1) 중 소수인 수를 의미한다. * **쌍둥이 소수** (twin prime) : 어떤 소수 p에 대해서 p+2도 소수일 때, 그 자연수 쌍을 의미한다. * **사촌 소수** (cousin prime) : 어떤 소수 p에 대해서 p+4도 소수일 때, 그 자연수 쌍을 의미한다. * **섹시 소수** (sexy prime) : 어떤 소수 p에 대해서 p+6도 소수일 때, 그 자연수 쌍을 의미한다. * **소피 제르맹 소수** (Sophie Germain prime) : 어떤 소수 p에 대해서, 2p+1도 소수인 경우를 의미한다. * **슈퍼 소수** (super-prime) : 어떤 자연수 x가 n번째 소수일 때, 그 소수의 순서 번호(순번)인 n도 소수인 경우, 즉 ‘**소수 번째 소수**’를 의미한다. * **Chen prime** * **페르마 소수** : 2를 2의 거듭제곱만큼 제곱한 수에 1을 더한 자연수(2^{2^n}+1) 중 소수인 수를 의미한다. * **프로트 소수** : 2의 거듭제곱에 그보다 작은 홀수를 곱하고 1을 더한 수(k \cdot 2^n + 1) 중 소수인 수를 의미한다. * **Pythagorean prime** * **서로 다른 세 소수의 제곱합과 같은 소수** A182479 : 1만보다 작은 소수 중 서로 다른 세 소수의 제곱합인 p^2 + q^2 + r^2의 형태로 나타낼 수 있는 수는 다음과 같다. :: 83, 179, 227, 347, 419, 467, 491, 563, 587, 659, 827, 971, 1019, 1091, 1259, 1427, 1499, 1667, 1811, 1907, 1979, 2027, 2243, 2267, 2339, 2531, 2579, 2699, 2819, 2843, 2939, 3347, 3539, 3659, 3779, 3851, 4019, 4091, 4259, 4451, 4523, 4547, 4691, 4787, 5099, 5171, 5387, 5507, 5867, 5939, 6011, 6299, 6779, 6899, 6947, 7019, 7187, 7211, 7307, 7547, 8147, 8219, 8291, 8747, 8819, 9059, 9467, 9539, 9587, …
# 미해결 문제들
소수와 관련된 많은 미해결 문제들이 있다. 대표적인 것들은 아래와 같다. * 골드바흐의 추측 * 쌍둥이 소수의 추측 * 메르센 소수의 무한성 * 홀수 완전수의 존재성
# 소수 개념의 확장
오래전부터 수학자들은 자연수 혹은 정수의 테두리 안에서만 소수 개념이 적용될 필요는 없다고 생각했다. 이것의 직접적 이유는, 다항식에 관한 이론이 체계화되면서 '기약다항식' 등 소수와 유사한 개념을 분석에 도입할 필요가 생겼기 때문이었다. 또한 유사한 시기에 추상대수학에 대해 기초적인 발전이 이루어지면서, 어떤 연산이 정의된 대수 구조에 대한 일반적 관점에서 소수 개념을 다룰 필요성 역시 생겨나기 시작했다. 소수의 개념을 분석해 나가던 도중, 수학자들은 이전에 자연수 범위에서만 사용되던 소수의 두 가지 정의가 좀 더 일반적인 경우에는 서로 동치조건이 아니게 된다는 사실을 발견하였다. 예컨대 자연수 범위 내에서 소수는, * p가 소수일 필요충분조건은, p가 1이 아니면서 p|m이고 m=ab를 만족하는 임의의 자연수 a,b에 대해 , p|a이거나 p|b인 것이다. * p가 소수일 필요충분조건은, p가 1이 아니면서 양의정수 a,b에 대해 p=ab이면 a나 b 둘 중에 오직 하나만이 1인 것이다. 와 같이 두 가지 방식으로 정의될 수 있다. 이 정의를 정수 범위로 확장시키기 위해서는 먼저 0을 제외하고, 단순히 정의에 들어 있는 1을 +1, -1 모두 포함하는 것으로 생각하면 된다. 이는 바로 정수환 상에서 각각 덧셈에 대한 항등원과 단원의 조건이다.(이 일반화를 직관적으로 좀 더 명확하게 받아들이기 위해서는, 가우스 정수에 대한 경우를 생각하면 된다. 이 때는 단위 순허수들까지 단원의 영역에 포함된다)
## 소수와 기약수
소수 개념은 이러한 이러한 일반화에 힘입어 일반적인 정역, 좀 더 나아가 **1을 가진 가환 환**까지 그 배경 집합이 확장될 수 있다. 그런데 이렇게 일반화하고 보면, 위에서 언급했던 바와 같이 위의 두 동치조건이 더 이상 동치가 아니게 된다. 그러므로 전자를 **소수**, 후자를 **기약수**로 정의하고(혹은 소원, 기약원이라고도 한다) 일반화된 정의를 서술하면 다음과 같다.(이하에서 0이란 주어진 환의 덧셈 연산에 해당하는 항등원이라는 의미이다) * p가 소수일 필요충분조건은, p가 0이나 단원이 아니면서 p|ab이면 p|a이거나 p|b인 것이다. * p가 기약수일 필요충분조건은, p가 0이나 단원이 아니면서 p=ab이면 a나 b의 둘 중 하나는 반드시 단원인 것이다. 이와 같은 정의는, 종래의 정수환과 가우스 정수환, 다항식환을 포괄하는 넓은 의미에서 적용될 수 있다.
## 몇몇 성질들
위와 같은 소수와 기약수에 대해, 어떤 1을 가진 가환 환 R위에서 다음 성질들이 성립한다. * 만약 R이 정역이면, R 위에서 소수는 모두 기약수다.(역은 일반적으로 성립하지 않는다) * 만약 R이 주 아이디얼 정역이면, R 위에서 소수와 기약수는 동치이다. 정수환은 주 아이디얼 정역이므로 정수환 위에서 소수와 기약수는 같다. * 만약 R이 체이면, R에 의해 유도된 다항식환 R[x]은 주 아이디얼 정역이므로, 윗 명제에 의해 R[x] 위에서 소수와 기약수는 동치이다.