소수(자연수)

누리위키, 온 누리의 백과사전
220.76.172.187 (토론)님의 2013년 11월 28일 (목) 12:57 판
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)

다른 뜻에 대해서는 소수 문서를 참조하십시오.


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

일반적인 정의[편집]

다음은 일반적인 정역(integral domain) \(D\)에서 0(항등원)이 아니고 가역원(unit)이 아닌 원소 \(p\)가 소원소라는 것은 \(D\) 임의의 원소 \(a\), \(b\)에 대해서 다음이 성립한다는 것이다.

  • \(p|ab \Longrightarrow p|a\) 또는 \(p|b\).

판별법[편집]

어떤 수가 소수임을 알기 위한 방법으로 약수의 수를 조사하는 것외에는 수학적으로 특별한 방법이 없다. 왜냐하면 소수의 일반적인 규칙이 알려지지 않았기 때문이다.[2] 가장 기본적인 소수의 판별법은 판별하려는 수보다 작은 모든 자연수로 그 수를 나누어 보는 것이다. 이때 1이 외에 나누어 떨어지는 수가 없다면, 그 수는 소수이다 하지만 위에 나온 방법은 매우 번거롭기때문에 더 짧은 시간안에 소수임을 판별하기위한 방법이 개발되고 있다. 일반적으로는 다음과 같은 과정을 거쳐서 소수를 판별한다.

  1. 2가 아닌 짝수는 소수가 아니다.[3]
  2. 판별하려는 수([math]n[/math]이라고 하자.)의 제곱근을 구한다. 이것을 [math]s[/math]라고 하자.
  3. [math]s[/math]정수이면 [math]n[/math]완전제곱수이므로 소수가 아니다.
  4. [math]s[/math]가 정수가 아니라면 [math]s[/math]보다 작은 모든 소수로 [math]n[/math]을 차례대로 나눈다.[4]
  5. 도중에 나누어 떨어지는 수가 있다면 [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. 찾고자 하는 범위의 자연수를 모두 나열한다. 1은 제외한다.
  2. 2를 제외한 2의 배수를 모두 지운다.
  3. 남은 수 중에서 가장 작은 수 [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

같이 보기[편집]

문제[편집]

특별한 수[편집]

주석[편집]

  1. ^ 엄밀한 의미로, 이것은 양의 소수만을 생각하는 것이다. 이것은 소인수분해의 유일성에 대해서 간단히 논하기 위해서이다.
  2. ^ 어떤 규칙이 있다면 그것을 만족하는지 확인하는 것만으로 알아낼 수 있다.
  3. ^ 짝수는 2로 나누어 떨어지기 때문이다.
  4. ^ [math]n[/math]보다 작은 수 중에서 무엇이 소수인지는 이미 알고있다고 가정할 수 있다. 만약 모른다면 [math]s[/math]보다 작은 모든 수로 나누어 보아야 한다.