소수 (수론) 문서 원본 보기

{{위키데이터 속성 추적}}
{{다른 뜻|3=0과 1 사이의 실수(小數, decimal), 또는 각각의 자리에 놓인 숫자와 소수점을 통해 나타낸 실수|1=소수 (기수법)}}
[[파일:Primes-vs-composites.svg|섬네일|오른쪽|좌측은 소수, 우측은 [[합성수]]. ...소수란 1보다 큰 자연수 중 1과 자기 자신만을 [[약수]]로 가지는 수다.]]
[[수론|정수론]]에서 '''소수'''(素數, 발음: [소쑤], {{문화어|씨수}}, {{llang|en|prime number|프라임 넘버}})는 1보다 큰 자연수 중 1과 자기 자신만을 [[약수]]로 가지는 수다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수다. 그러나 6은 자신보다 작은 두 숫자의 곱(2×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 [[합성수|합성수나 비소수]]라고 한다.

[[산술의 기본 정리]]의 '1보다 큰 모든 자연수는 그 자체가 소수이거나, 순서를 무시하고 유일한 소인수의 조합을 갖는다'는 내용을 바탕으로 [[정수론]]에서는 매우 중요한 주제로 다루어진다. 또한 현대에는 암호 분야에서의 기술적 사용으로 그 중요성이 부각되고 있다.

소수의 개수는 무한하며, 이는 [[유클리드의 정리]]에 의하여 최초로 논증되었다. 소수와 합성수를 구분해낼 수 있는 명확한 공식은 지금까지도 밝혀지지 않은 상태이나, 대역적으로 자연수 중 소수의 비율의 근사치를 예측하는 모델로는 여러가지가 알려져 있다. 이러한 방향으로의 연구의 첫 결과는 19세기 말에 증명된 [[소수 정리]]인데, 이는 무작위로 선택된 한 수가 소수일 확률은 그 수의 자릿수, 곧 로그값에 반비례함을 알려준다.

== 소수 목록 ==
{{본문|소수 목록}}
1000보다 작은 소수는 다음과 같다. {{OEIS|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개임이 밝혀져 있다.

== 소인수 분해 ==
{{본문|소인수 분해}}

[[정수론의 기본 정리]]에 의해, 모든 [[자연수]]는 꼭 한가지 방법으로 소수의 [[곱]]으로 표현할 수 있고 이를 [[소인수 분해]]의 [[산술의 기본 정리|일의성]]이라고 한다. 즉, 곱셈의 관점에서 소수는 자연수를 이루는 성분이다.

예를 들면,

:<math>23244 = 2^2 \times 3 \times 13 \times 149</math>

이고 23244는 (약수의 순서를 무시하면) 단 한 가지 방법으로 소인수분해된다. 이 정리의 중요성은 소수들의 집합에서 1을 제외하는 이유 중의 하나다. 만일 1이 소수라면 이 정리의 엄밀한 진술을 위해 추가적인 제한조건을 필요로 하기 때문이다.

== 소수의 개수 ==
소수는 [[무한]]하다. 이 명제를 [[유클리드의 정리]]라고 하며 가장 오래된 증명은 그리스 [[수학자]] [[유클리드]]의 《[[유클리드 원론]]》(제9권, 정리 20)에서 볼 수 있다. 유클리드의 증명은 “어느 주어진 [[유한]]한 소수들 보다 더 많다.”라는 결론으로 표현되고, 그의 증명은 본래 아래와 같다.

{{인용문|유한 개의 소수가 존재한다고 가정하자. 이 유한 개의 소수들을 모두 곱한 값에 1을 더한다. ([[유클리드 수]] 참조) 그 결과값은 다른 어떤 소수로 나누어도 나머지가 1이므로 어떤 소수로도 나누어떨어지지 않는 수가 된다. 따라서 이 수가 소수라면 기존의 최대소수보다 큰 소수가 있다는 것이 증명되고, 이 수가 소수가 아니라고 해도 또다른 소수가 있어야 한다는 것을 의미하기 때문에 소수가 유한하다는 애초 가정에 모순이 존재함을 알 수 있다.}}

다른 수학자들도 각자의 증명을 내놓았다. 그 중 [[레온하르트 오일러|오일러]]에 의한 증명은 모든 소수들의 역수의 합이 발산한다는 증명으로부터 소수의 개수가 무한함을 보였다.

== 역사 ==
소수에 대한 최초의 기록은 [[고대 이집트]] 파피루스에서 찾을 수 있다. 파피루스에는 소수와 합성수를 구분해서 다른 형태로 표기되어 있었다. 그러나 소수에 대한 본격적인 연구는 [[고대 그리스]]에서 본격적으로 시작되었다. 《[[유클리드 원론]]》(기원전 300년경)에는 소수가 무한히 많다는 내용과 [[정수론의 기본 정리]]가 포함되어 있다. 유클리드는 [[메르센 소수]]로부터 [[완전수]]를 만드는 방법도 설명하였다.

유클리드 이후 17세기까지 소수에 대한 연구는 별로 없었다. 그러나 [[피에르 드 페르마|페르마]]는 1640년에 [[페르마 소정리]]를 증명없이 발표하였다.

== 소수 찾기 ==
현재까지 알려진 가장 간단한 방법으로 [[에라토스테네스의 체]]가 있다. 방법은 다음과 같다.
# 찾고자 하는 범위의 자연수를 나열한다.
#1은 지운다.
# 2부터 시작하여, 2의 배수를 지워나간다.
# 다음 소수의 배수를 모두 지운다.
이를 반복하여 마지막까지 지우면, 남는 수들이 소수가 된다. 이 과정은 사실 어떤 자연수 <math>n</math>이 소수임을 판정하기 위해서 <math>\lfloor\sqrt{n}\rfloor</math>까지만 진행하면 되는데<ref>여기서 어떤 실수 <math>x</math>에 대해, <math>\lfloor x \rfloor</math>는 <math>x</math>보다 작거나 같은 수들 중 가장 큰 정수를 뜻한다. 이를 [[바닥 함수]]라 한다.</ref>, 수가 수를 나누기 위해서는 그 몫이 항상 필요하며 나누는 수와 몫 중 어느 하나는 반드시 <math>\sqrt{n}</math> 이하이기 때문이다. 아래 표로 이 방법을 활용하면 다음과 같이 된다.(4, 6, 8, 10은 제외(무조건 합성수기에<ref>넣어봤자 의미가 없다는 뜻이다.</ref>))
{|
|+소수 표
|<s>1</s><ref>소수도, 합성수도 아님</ref>
|2
|3
|5
|7
|<s>9</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|-
|11
|<s>12</s><ref name=":1">2로 인해 합성수 판결</ref>
|13
|<s>15</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|17
|19
|-
|<s>21</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|<s>22</s><ref name=":1">2로 인해 합성수 판결</ref>
|23
|<s>25</s><ref name=":2">5로 인해 합성수 판결</ref>
|<s>27</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|29
|-
|31
|<s>32</s><ref name=":1">2로 인해 합성수 판결</ref>
|<s>33</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|<s>35</s><ref name=":2">5로 인해 합성수 판결</ref>
|37
|<s>39</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|-
|41
|<s>42</s><ref name=":1">2로 인해 합성수 판결</ref>
|43
|<s>45</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|47
|<s>49</s><ref name=":3">7로 인해 합성수 판결</ref>
|-
|<s>51</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|<s>52</s><ref name=":1">2로 인해 합성수 판결</ref>
|53
|<s>55</s><ref name=":2">5로 인해 합성수 판결</ref>
|<s>57</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|59
|-
|61
|<s>62</s><ref name=":1">2로 인해 합성수 판결</ref>
|<s>63</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|<s>65</s><ref name=":2">5로 인해 합성수 판결</ref>
|67
|<s>69</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|-
|71
|<s>72</s><ref name=":1">2로 인해 합성수 판결</ref>
|73
|<s>75</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|<s>77</s><ref name=":3">7로 인해 합성수 판결</ref>
|79
|-
|<s>81</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|<s>82</s><ref name=":1">2로 인해 합성수 판결</ref>
|83
|<s>85</s><ref name=":2">5로 인해 합성수 판결</ref>
|<s>87</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|89
|-
|<s>91</s><ref name=":3">7로 인해 합성수 판결</ref>
|<s>92</s><ref name=":1">2로 인해 합성수 판결</ref>
|<s>93</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|<s>95</s><ref name=":2">5로 인해 합성수 판결</ref>
|97
|<s>99</s><ref name=":0">3으로 인해 합성수 판결.</ref>
|}
소수를 골라내기 위한 방법은 다음과 같다. 이 방법을 이용해 소수를 어느 정도 골라낼 수 있다.
# 2와 5를 제외하면, 모든 소수의 일의 자리 수는 1, 3, 7, 9다.
# 어떤 자연수 <math>n</math>이 소수임을 판정하기 위해선 <math>\sqrt{n}</math>까지의 수 중 1을 제외하고 그 자연수의 약수가 있는지 확인하면 된다.
# [[배수]]의 성질을 이용하면 쉽게 구할 수도 있다.

그 외에도 다양하고 복잡한 판정법이 존재하지만, 위의 세 가지는 당연하고 간단한 것들이다.

== 소수의 종류 및 관련 성질 ==
모든 소수를 분류해서 해당 집합에 넣는 것은 아니지만, 일반적으로 알려진 특수한 소수에는 다음이 있다.

* '''가우스 소수''' (Gaussian prime)
: [[가우스 정수]] 중 가우스 정수의 곱으로 나타낼 수 없는 수를 의미한다.

* '''[[메르센 소수]]''' (Mersenne prime)
: 2의 거듭제곱보다 1 작은 자연수(<math>2^n - 1</math>) 중 소수인 수를 의미한다.

* '''[[쌍둥이 소수]]''' (twin prime)
: 어떤 소수 <math>p</math>에 대해서 <math>p+2</math>도 소수일 때, 그 자연수 쌍을 의미한다.

* '''[[사촌 소수]]''' (cousin prime)
: 어떤 소수 <math>p</math>에 대해서 <math>p+4</math>도 소수일 때, 그 자연수 쌍을 의미한다.

* '''[[섹시 소수]]''' (sexy prime)
: 어떤 소수 <math>p</math>에 대해서 <math>p+6</math>도 소수일 때, 그 자연수 쌍을 의미한다.

* '''[[소피 제르맹 소수]]''' (Sophie Germain prime)
: 어떤 소수 <math>p</math>에 대해서, <math>2p+1</math>도 소수인 경우를 의미한다.

* '''[[슈퍼 소수]]''' (super-prime)
: 어떤 자연수 <math>x</math>가 <math>n</math>번째 소수일 때, 그 소수의 순서 번호(순번)인 <math>n</math>도 소수인 경우, 즉 ‘'''소수 번째 소수'''’를 의미한다.

* '''{{임시링크|첸 소수|en|Chen prime}}'''

* '''[[페르마 소수]]'''
: 2를 2의 거듭제곱만큼 제곱한 수에 1을 더한 자연수(<math>2^{2^n}+1</math>) 중 소수인 수를 의미한다.

* '''[[프로트 소수]]'''
: 2의 거듭제곱에 그보다 작은 홀수를 곱하고 1을 더한 수(<math>k \cdot 2^n + 1</math>) 중 소수인 수를 의미한다.

* '''{{임시링크|피타고라스 소수|en|Pythagorean prime}}'''

* '''서로 다른 세 소수의 제곱합과 같은 소수''' {{OEIS|A182479}}
: 1만보다 작은 소수 중 서로 다른 세 소수의 제곱합인 <math>p^2 + q^2 + r^2</math>의 형태로 나타낼 수 있는 수는 다음과 같다.
:: [[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]], …

== 미해결 문제들 ==
소수와 관련된 많은 미해결 문제들이 있다. 대표적인 것들은 아래와 같다.

* [[골드바흐의 추측]]
* [[쌍둥이 소수의 추측]]
* [[메르센 소수]]의 무한성
* 홀수 [[완전수]]의 존재성

== 소수 개념의 확장 ==
오래전부터 수학자들은 자연수 혹은 정수의 테두리 안에서만 소수 개념이 적용될 필요는 없다고 생각했다. 이것의 직접적 이유는, [[다항식]]에 관한 이론이 체계화되면서 '[[기약다항식]]' 등 소수와 유사한 개념을 분석에 도입할 필요가 생겼기 때문이었다. 또한 유사한 시기에 [[추상대수학]]에 대해 기초적인 발전이 이루어지면서, 어떤 [[연산 (수학)|연산]]이 정의된 [[대수 구조]]에 대한 일반적 관점에서 소수 개념을 다룰 필요성 역시 생겨나기 시작했다.

소수의 개념을 분석해 나가던 도중, 수학자들은 이전에 자연수 범위에서만 사용되던 소수의 두 가지 정의가 좀 더 일반적인 경우에는 서로 동치조건이 아니게 된다는 사실을 발견하였다. 예컨대 자연수 범위 내에서 소수는,
* <math>p</math>가 소수일 필요충분조건은, <math>p</math>가 <math>1</math>이 아니면서 <math>p|m</math>이고 <math>m=ab</math>를 만족하는 임의의 자연수 <math>a</math>,<math>b</math>에 대해 , <math>p|a</math>이거나 <math>p|b</math>인 것이다.
* <math>p</math>가 소수일 필요충분조건은, <math>p</math>가 <math>1</math>이 아니면서 양의정수 <math>a</math>,<math>b</math>에 대해 <math>p=ab</math>이면 <math>a</math>나 <math>b</math> 둘 중에 오직 하나만이 1인 것이다.
와 같이 두 가지 방식으로 정의될 수 있다. 이 정의를 정수 범위로 확장시키기 위해서는 먼저 <math>0</math>을 제외하고, 단순히 정의에 들어 있는 <math>1</math>을 <math>+1, -1</math> 모두 포함하는 것으로 생각하면 된다. 이는 바로 정수환 상에서 각각 덧셈에 대한 [[항등원]]과 [[단원]]의 조건이다.(이 일반화를 직관적으로 좀 더 명확하게 받아들이기 위해서는, [[가우스 정수]]에 대한 경우를 생각하면 된다. 이 때는 단위 순허수들까지 단원의 영역에 포함된다)

=== 소수와 기약수 ===
소수 개념은 이러한 이러한 일반화에 힘입어 일반적인 [[정역]], 좀 더 나아가 '''1을 가진 가환 환'''까지 그 배경 집합이 확장될 수 있다. 그런데 이렇게 일반화하고 보면, 위에서 언급했던 바와 같이 위의 두 동치조건이 더 이상 동치가 아니게 된다. 그러므로 전자를 '''소수''', 후자를 '''기약수'''로 정의하고(혹은 소원, 기약원이라고도 한다) 일반화된 정의를 서술하면 다음과 같다.(이하에서 <math>0</math>이란 주어진 환의 덧셈 연산에 해당하는 항등원이라는 의미이다)
* <math>p</math>가 소수일 필요충분조건은, <math>p</math>가 <math>0</math>이나 단원이 아니면서 <math>p|ab</math>이면 <math>p|a</math>이거나 <math>p|b</math>인 것이다.
* <math>p</math>가 기약수일 필요충분조건은, <math>p</math>가 <math>0</math>이나 단원이 아니면서 <math>p=ab</math>이면 <math>a</math>나 <math>b</math>의 둘 중 하나는 반드시 단원인 것이다.
이와 같은 정의는, 종래의 정수환과 가우스 정수환, [[다항식환]]을 포괄하는 넓은 의미에서 적용될 수 있다.

=== 몇몇 성질들 ===
위와 같은 소수와 기약수에 대해, 어떤 1을 가진 가환 환 <math>R</math>위에서 다음 성질들이 성립한다.
* 만약 <math>R</math>이 정역이면, <math>R</math> 위에서 소수는 모두 기약수다.(역은 일반적으로 성립하지 않는다)
* 만약 <math>R</math>이 [[주 아이디얼 정역]]이면, <math>R</math> 위에서 소수와 기약수는 동치이다. 정수환은 주 아이디얼 정역이므로 정수환 위에서 소수와 기약수는 같다.
* 만약 <math>R</math>이 [[체 (수학)|체]]이면, <math>R</math>에 의해 유도된 다항식환 <math>R[x]</math>은 주 아이디얼 정역이므로, 윗 명제에 의해 <math>R[x]</math> 위에서 소수와 기약수는 동치이다.

== 같이 보기 ==
{{위키공용분류}}
* [[메르텐스 정리 (수론)]]
* [[반소수]]
* [[소수 정리]]
* [[소 아이디얼]]
* [[수소 (수학)]]
* [[코플랜드 에르되시 상수|코플랜드-에르되시 상수]]
* [[회문 소수]]

== 각주 ==
{{각주}}

== 참고 문헌 ==
* 김주필, 『알기 쉬운 대수학』, 도서출판 대선, 2002
* 김응태, 박승안, 『현대대수학(6/e)』, 경문사, 2006

== 외부 링크 ==
{{포털|수학}}
* [http://www.gutenberg.org/etext/65 10만 번째 소수까지] ([[구텐베르크 프로젝트]])
* [https://terms.naver.com/entry.naver?docId=3566952&cid=58944&categoryId=58970 네이버 캐스트 - 소수가 뭐길래?]
* [http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php 소수리스트1,000,000,000,000개-소수 12째자리]

{{수 체계}}
{{소수}}
{{전거 통제}}

[[분류:소수| ]]
[[분류:정수열]]