소수 (수론)

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

수학의 수 체계
기초
$\mathbb{N}\sub\mathbb{Z}\sub\mathbb{Q}\sub\mathbb{R}\sub\mathbb{C}$ $\mathbb{N}$ 자연수 {1,2,3...} $\mathbb{P}$ 소수 {2,3,5,7,...} $\mathbb{Z}$ 정수 {...,-1,0,1,...} $\mathbb{Q}$ 유리수 {2/3,-4/7,...} 무리수 $\mathbb{R}$ 실수( $\mathbb{Z} , \mathbb{Q} , \sqrt2, \pi$ ) 허수 $\mathbb{C}$ 복소수 $\mathbb{R}(\mathrm{i})$ 작도 가능한 수 대수적 수 초월수 초한수 계산 가능한 수
복소수의 확장
이원수 다원수 사원수 팔원수 16원수 Superreal 초실수 Surreal
기타
명목수 서수 size, position {n} 기수 $\{ \aleph_0, \aleph_1, \aleph_2, \cdots \}$ p진수 정수열 수학 상수 $i$ 허수 단위 $= \sqrt{-1}$ π 파이 ≈ 3.14159 26535 ... e (상수) ≈ 2.71828 (∉ $\mathbb{Q}$ ) ∞ 무한대
주요 상수
π - e - √2 - √3 - γ - φ - β^* - δ - α - C₂ - M₁ - B₂ - B₄ - Λ - K - K - K - B´_L - μ - E_B - Ω - β - λ - 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자리 정수가 소수일 확률은 얼마인가요?" 같은 질문을 던질 수 있다. 이런 질문에 대한 답은 소수 정리로부터 얻을 수 있다.