소수 (원본) (1) - 시드위키

[[분류:가져온 문서/오메가]]
素數 / Prime number

1과 자기 자신만을 양의 약수로 가지는 자연수이다. 1은 소인수분해의 유일성에 어긋나므로 소수가 아니다. 100까지의 처음 25개의 소수는 다음과 같다.
>[[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…
여기서, 2는 유일한 짝수 소수이다.

== 소수의 개수 ==
소수의 개수는 무한하다. 이에 대한 다양한 증명이 있다. 가장 간단한 증명은 유클리드의 것으로 알려져 있다.

=== 증명 1 ===
모든 자연수 [math(n)]은 소인수분해하면 소수들의 곱으로 표현되므로
><math>\frac{1}{1^s}+\frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\cdots=	\left( \frac{1}{2^0}+\frac{1}{2^s}+\frac{1}{2^{2s}}+\cdots \right)\left( \frac{1}{3^0}+\frac{1}{3^s}+\frac{1}{3^{2s}}+\cdots \right)\left( \frac{1}{5^0}+\frac{1}{5^s}+\frac{1}{5^{2s}}+\cdots \right) \cdots</math>
><math>\sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p}\frac{1}{(1-1/p^s)}</math>
><math> \sum_{n=1}^{\infty} n^{-s} = \prod_{p}(1-p^{-s})^{-1} </math>
이제 소수의 개수가 유한하다고 가정하고 [math(s)]가 [math(1)]로 가는 극한을 취하면 좌변은 양의 무한으로 발산하지만 우변은 어떤 실수로 수렴하게 되므로 모순이 발생한다.

=== 증명 2 ===
'''Definition''' 정수 [math(m,\ r\ (m \geq 1))]에 대하여, [math(r+m \mathbb{Z})]를 [math(\{r+mn|n \in \mathbb{Z} \})]로 정의한다. 이런 집합을 등차수열(AP)라 한다.
정수 [math(m \geq 2)]에 대하여 [math(\text{NM}(m) = (1 + m\mathbb{Z}) \cup (2 + m\mathbb{Z}) \cup \cdots \cup ((m-1) + m\mathbb{Z}))]라 정의한다, [math(\text{NM}(m))]은 [math(m)]으로 나누어 떨어지지 않는 정수의 집합이다.

'''Claim''' 유한한 개수의 AP의 교집합은 공집합이거나 무한집합이다.

'''Proof''' AP들을 [math(r_i+m_i\mathbb{Z}\ (1 \leq i \leq n))]라 하자. [math(\displaystyle \bigcap_{i=1}^n \left( r_i + m_i \mathbb{Z} \right))]가 공집합이면 증명이 끝난다. 공집합이 아니어서 원소 [math(x)]가 존재한다면 [math(x)]와 [math(\text{mod}\ m_1m_2 \cdots m_n)]에 대하여 합동인 모든 정수들이 [math(\displaystyle \bigcap_{i=1}^n \left( r_i + m_i \mathbb{Z} \right))]의 원소가 되므로 [math(\displaystyle \bigcap_{i=1}^n \left( r_i + m_i \mathbb{Z} \right))]는 무한집합이 된다. 따라서 증명이 끝났다.

'''Theorem''' 소수의 개수는 무한하다.

'''Proof''' 소수의 개수가 유한하여 [math(p_1,\ p_2,\ \cdots ,\ p_k)]가 있다고 가정하자. 그리고 [math(\displaystyle\bigcap_{i=1}^{k} \text{NM}(p_i))]를 생각해보자. [math(\displaystyle\bigcap_{i=1}^{k} \text{NM}(p_i))]의 원소는 모든 [math(p_i)]에 대해 나누어 떨어지지 않아야 하므로 [math(\bigcap_{i=1}^{k} \text{NM}(p_i)= \{1,-1\})]이 된다. 하지만 [math(\displaystyle \bigcap_{i=1}^{k} \text{NM}(p_i) = \bigcap_{i=1}^{k} \left[ (1 + p_i \mathbb{Z}) \cup (2 + p_i \mathbb{Z}) \cup \cdots \cup ((p_i - 1) + p_i \mathbb{Z}) \right])]이고, [math(\bigcup)]과 [math(\bigcap)]은 분배법칙이 성립하므로 [math(\displaystyle\bigcap_{i=1}^{k} \left[ (1 + p_i \mathbb{Z}) \cup (2 + p_i \mathbb{Z}) \cup \cdots \cup ((p_i - 1) + p_i \mathbb{Z}) \right])]는 유한개의 AP들의 교집합들의 합집합이 된다. 각 유한개의 AP들의 교집합은 

'''Claim'''에 의해 공집합 혹은 무한집합이므로, 그 합집합 또한 공집합 혹은 무한집합이 된다. 하지만 [math(\{1.-1\})]은 공집합도 무한집합도 아니므로 모순이 발생한다. 따라서 소수의 개수는 무한하다.

=== 증명 3 ===
[math(\mathbb{P})]가 모든 소수의 집합이라고 하자. [math(\mathbb{P})]가 유한집합이라고 가정하면 [math(|\mathbb{P}|=n)]이라 할 때 [math(\mathbb{P}=\{p_1, p_2, \cdots, p_n\})]이라고 쓸 수 있다. [math(N=p_1 p_2 \cdots p_n + 1)]이라고 하면 [math(N\not\equiv 0 \ (\text{mod} \ p_i)\ (i\in \mathbb{N}, 1\leq i \leq n))]이다.
따라서 [math(N)]은 어느 소수로도 나누어지지 않으므로, [math(N)]이 소수이거나 또는 [math(N)]을 나누는 [math(\mathbb{P})]에 속하지 않는 소수가 존재하므로 [math(\mathbb{P})]가 모든 소수의 집합이라는 데 모순이다. 따라서 [math(\mathbb{P})]는 무한집합이다.

== 소수 정리 ==
소수 정리는 소수들의 분포를 잘 알려주는 정리로,
><math>\lim_{x\to \infty}\frac{\pi(x)\ln{x}}{x}=1</math>
가 된다는 정리이다.

== 영상 ==
[youtube(EZCoiIl_ZJs)]

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]