소수(자연수) 편집하기

{{다른 뜻|소수}}
'''소수'''(素數, primes)는 [[1]]보다 큰 [[자연수]] 중에서 양의 [[약수]]가 [[1]]과 자신밖에 없는 수이다. [[2]]를 제외한 다른 소수는 모두 [[홀수]]이다.

== 판별법 ==
어떤 수가 소수임을 알기 위한 방법으로 [[약수]]의 수를 조사하는 것외에는 수학적으로 특별한 방법이 없다. 왜냐하면 소수의 일반적인 규칙이 알려지지 않았기 때문이다.<ref>어떤 규칙이 있다면 그것을 만족하는지 확인하는 것만으로 알아낼 수 있다.</ref> 가장 기본적인 소수의 판별법은 판별하려는 수보다 작은 모든 자연수로 그 수를 나누어 보는 것이다. 이때 [[1]]이 외에 나누어 떨어지는 수가 없다면, 그 수는 소수이다 하지만 위에 나온 방법은 매우 번거롭기때문에 더 짧은 시간안에 소수임을 판별하기위한 방법이 개발되고 있다. 일반적으로는 다음과 같은 과정을 거쳐서 소수를 판별한다.
# [[2]]가 아닌 [[짝수]]는 소수가 아니다.<ref>짝수는 2로 나누어 떨어지기 때문이다.</ref>
# 판별하려는 수(<math>n</math>이라고 하자.)의 제곱근을 구한다. 이것을 <math>s</math>라고 하자.
# <math>s</math>가 [[정수]]이면 <math>n</math>은 [[사각수|완전제곱수]]이므로 소수가 아니다.
# <math>s</math>가 정수가 아니라면 <math>s</math>보다 작은 모든 소수로 <math>n</math>을 차례대로 나눈다.<ref><math>n</math>보다 작은 수 중에서 무엇이 소수인지는 이미 알고있다고 가정할 수 있다. 만약 모른다면 <math>s</math>보다 작은 모든 수로 나누어 보아야 한다.</ref>
# 도중에 나누어 떨어지는 수가 있다면 <math>n</math>은 소수가 아니다. 나누어 떨어지는 수가 없다면 <math>n</math>은 소수이다.
다음은 위 판별법이 옳음을 증명한 것이다.
:만약 <math>\sqrt{n}</math>보다 큰 소수중에서 <math>n</math>을 나누는 수 <math>p</math>가 있다면, <math> \frac{n}{p} </math>는 <math>\sqrt{n}</math>보다 작은 수이다.
:그러므로 <math> \frac{n}{s} </math>를 [[소인수분해]]하면 반드시 <math>\sqrt{n}</math>보다 작거나 같은 소인수가 존재하게 된다.
:즉, <math>\sqrt{n}</math>보다 작은 소수로 나누어 보는 과정에서 이미 나누어떨어진다.
:이것은 <math>\sqrt{n}</math>보다 작은 수로만 나누어 보면 된다는 뜻이다.

=== 에라토스테네스의 체 ===
'''에라토스테네스의 체'''는 유한한 범위안에 있는 자연수 중에서 소수인 것을 모두 찾아내는 방법이다. 방법은 아주 간단하다.
# 찾고자 하는 범위의 자연수를 모두 나열한다. 1은 제외한다.
# 2를 제외한 2의 [[배수]]를 모두 지운다.
# 남은 수 중에서 가장 작은 수 <math>p</math>를 제외한 <math>p</math>의 배수를 모두 지운다.
이 과정을 거쳐서 남아있는 수는 모두 소수이다.

== 소수의 개수 ==
소수의 개수가 무수히 많다는 것이 증명된 것은 매우 오래전의 일이다. 가장 오래되고 유명한 증명인 [[유클리드]]의 증명은 현대식으로 표현하면 다음과 같다.
:소수의 개수가 유한하다고 가정하고 작은 것부터 각각 <math>p_1,\ p_2,\ \cdots,\ p_n</math>이라고 하자.
:자연수 <math>P = p_1 p_2 \cdots p_n + 1</math>이라고 하자.
:소수는 0이 아니므로, <math>P</math>는 가장 큰 소수보다 크다.
:그런데 <math>P</math>를 어떤 소수로 나누어도 나머지가 1이 되므로, <math>P</math>는 소수이어야한다.
:즉, 처음에 주어진 소수들보다 더 큰 소수가 존재하는데, 이것은 모순이다. 이 모순을 해소하려면 소수가 무수히 많아야한다.
이 방법 외에도 많은 수학자들이 여러가지 방법으로 소수의 개수가 무수히 많다는 것을 증명하였다.

== 처음 100개의 소수 ==
[[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

== 같이 보기 ==
* [[소인수분해]]
* [[쌍둥이 소수]]

=== 문제 ===
* [[골트바흐의 추측]]
* [[리만 가설]]

=== 특별한 수 ===
* [[메르센 수]]
* [[페르마 수]]

== 주석 ==
<references/>

[[분류:수학]]
[[분류:정수]]