소수 (수론)

위키백과 ― 우리 모두의 백과사전.

수학 체계
기초

\mathbb{N}\sub\mathbb{Z}\sub\mathbb{Q}\sub\mathbb{R}\sub\mathbb{C}

복소수의 확장
기타

i 허수단위 = \sqrt{-1}
π 파이 ≈ 3.14159 26535 ...
e (상수) ≈ 2.71828 (∉ \mathbb{Q})
무한대

주요 상수

π - e - √2 - √3 - γ -
φ - β* - δ - α - C2 -
M1 - B2 - B4 - Λ - K -
K - K - B´L - μ -
EB -
Ω - β - λ - D(1) - λμ -
Cah. - Lap. - A-G - Λ - K-L -
Apr. - θ - Bac. - Prt. - Lb. -
Niv. - Sie. - Kin. - F - L

소수(素數, 문화어: 씨수, prime number)는 약수가 1과 자기 자신 뿐인 1보다 큰 자연수로 정의된다. 정수론에서 매우 중요한 역할을 담당한다.현재에 와서는 암호 분야에서의 사용으로 그 중요성이 부각되고 있다.

100까지의 처음 25개의 소수는 다음과 같다. (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...

목차

[편집] 소수의 곱으로 자연수를 표현하기

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

예를 들면,

23244 = 2^2 \times 3 \times 13 \times 149

이고 23244는 (약수의 순서를 무시하면) 단 한 가지 방법으로 소인수분해 된다. 실제로 소인수분해를 하는 자세한 방법은 소인수분해 알고리즘을 참고하라.

이 정리의 중요성은 소수들의 집합에서 1을 제외하는 이유 중의 하나이다. 만일 1이 소수라면 이 정리의 엄밀한 진술을 위해 추가적인 제한조건을 필요로 하기 때문이다.

[편집] 얼마나 많은 소수가 있을까?

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

유한 개의 소수가 존재한다고 가정하자. 이 유한 개의 소수들을 모두 곱한 값에 1을 더한다. (유클리드 수 참조) 그 결과값은 다른 어떤 소수로 나누어도 나머지가 1이므로 어떤 소수로도 나누어 떨어지지 않는 수가 된다. 따라서 이 수 역시 소수이며, 애초에 가정한 유한한 소수 집합에 존재하지 않는다. 그러므로 소수가 유한하다는 애초 가정에 모순이 존재함을 알 수 있다.

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

소수의 개수는 무한하지만, 어떤 이는 "100,000 이하에 몇 개 정도의 소수가 존재하나요?" 또는 "100자리 정수가 소수일 확률은 얼마인가요?" 같은 질문을 던질 수 있다. 이런 질문에 대한 답은 소수 정리로부터 얻을 수 있다.

[편집] 소수를 찾는 방법

[편집] 에라토스테네스의 체

가장 간단한 방법으로,

  1. 찾고자 하는 범위의 자연수를 나열한다.
  2. 2부터 시작하여, 2의 배수를 지워나간다.
  3. 다음 수의 배수를 모두 지운다.

이를 반복하여 마지막까지 지우면, 남는 수들이 소수가 된다.

[편집] 미해결 문제들

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

[편집] 바깥 고리


이 문서는 수학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해갑시다.