소수(자연수)
다른 뜻에 대해서는 소수 문서를 참조하십시오.
소수(素數, primes)는 1보다 큰 자연수 중에서 양의 약수가 1과 자신밖에 없는 수이다. 2를 제외한 다른 소수는 모두 홀수이다.[1]
일반적인 정의[편집]
다음은 일반적인 정역(integral domain) \(D\)에서 0(항등원)이 아니고 가역원(unit)이 아닌 원소 \(p\)가 소원소라는 것은 \(D\) 임의의 원소 \(a\), \(b\)에 대해서 다음이 성립한다는 것이다.
- \(p|ab \Longrightarrow p|a\) 또는 \(p|b\).
판별법[편집]
어떤 수가 소수임을 알기 위한 방법으로 약수의 수를 조사하는 것외에는 수학적으로 특별한 방법이 없다. 왜냐하면 소수의 일반적인 규칙이 알려지지 않았기 때문이다.[2] 가장 기본적인 소수의 판별법은 판별하려는 수보다 작은 모든 자연수로 그 수를 나누어 보는 것이다. 이때 1이 외에 나누어 떨어지는 수가 없다면, 그 수는 소수이다 하지만 위에 나온 방법은 매우 번거롭기때문에 더 짧은 시간안에 소수임을 판별하기위한 방법이 개발되고 있다. 일반적으로는 다음과 같은 과정을 거쳐서 소수를 판별한다.
- 2가 아닌 짝수는 소수가 아니다.[3]
- 판별하려는 수([math]n[/math]이라고 하자.)의 제곱근을 구한다. 이것을 [math]s[/math]라고 하자.
- [math]s[/math]가 정수이면 [math]n[/math]은 완전제곱수이므로 소수가 아니다.
- [math]s[/math]가 정수가 아니라면 [math]s[/math]보다 작은 모든 소수로 [math]n[/math]을 차례대로 나눈다.[4]
- 도중에 나누어 떨어지는 수가 있다면 [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