(+)분류 : 가져온 문서/오메가
素數 / Prime number
1과 자기 자신만을 양의 약수로 가지는 자연수이다. 1은 소인수분해의 유일성에 어긋나므로 소수가 아니다. 100까지의 처음 25개의 소수는 다음과 같다.
여기서, 2는 유일한 짝수 소수이다.
1. 소수의 개수 ✎ ⊖
소수의 개수는 무한하다. 이에 대한 다양한 증명이 있다. 가장 간단한 증명은 유클리드의 것으로 알려져 있다.
1.1. 증명 1 ✎ ⊖
모든 자연수 n은 소인수분해하면 소수들의 곱으로 표현되므로
이제 소수의 개수가 유한하다고 가정하고 s가 1로 가는 극한을 취하면 좌변은 양의 무한으로 발산하지만 우변은 어떤 실수로 수렴하게 되므로 모순이 발생한다.
\\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
\\sum_{n=1}^{\\infty} \\frac{1}{n^s} = \\prod_{p}\\frac{1}{(1-1/p^s)}
\\sum_{n=1}^{\\infty} n^{-s} = \\prod_{p}(1-p^{-s})^{-1}
이제 소수의 개수가 유한하다고 가정하고 s가 1로 가는 극한을 취하면 좌변은 양의 무한으로 발산하지만 우변은 어떤 실수로 수렴하게 되므로 모순이 발생한다.
1.2. 증명 2 ✎ ⊖
Definition 정수 m,\\ r\\ (m \\geq 1)에 대하여, r+m \\mathbb{Z}를 \\{r+mn|n \\in \\mathbb{Z} \\}로 정의한다. 이런 집합을 등차수열(AP)라 한다.
정수 m \\geq 2에 대하여 \\text{NM}(m) = (1 + m\\mathbb{Z}) \\cup (2 + m\\mathbb{Z}) \\cup \\cdots \\cup ((m-1) + m\\mathbb{Z})라 정의한다, \\text{NM}(m)은 m으로 나누어 떨어지지 않는 정수의 집합이다.
Claim 유한한 개수의 AP의 교집합은 공집합이거나 무한집합이다.
Proof AP들을 r_i+m_i\\mathbb{Z}\\ (1 \\leq i \\leq n)라 하자. \\displaystyle \\bigcap_{i=1}^n \\left( r_i + m_i \\mathbb{Z} \\right)가 공집합이면 증명이 끝난다. 공집합이 아니어서 원소 x가 존재한다면 x와 \\text{mod}\\ m_1m_2 \\cdots m_n에 대하여 합동인 모든 정수들이 \\displaystyle \\bigcap_{i=1}^n \\left( r_i + m_i \\mathbb{Z} \\right)의 원소가 되므로 \\displaystyle \\bigcap_{i=1}^n \\left( r_i + m_i \\mathbb{Z} \\right)는 무한집합이 된다. 따라서 증명이 끝났다.
Theorem 소수의 개수는 무한하다.
Proof 소수의 개수가 유한하여 p_1,\\ p_2,\\ \\cdots ,\\ p_k가 있다고 가정하자. 그리고 \\displaystyle\\bigcap_{i=1}^{k} \\text{NM}(p_i)를 생각해보자. \\displaystyle\\bigcap_{i=1}^{k} \\text{NM}(p_i)의 원소는 모든 p_i에 대해 나누어 떨어지지 않아야 하므로 \\bigcap_{i=1}^{k} \\text{NM}(p_i)= \\{1,-1\\}이 된다. 하지만 \\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]이고, \\bigcup과 \\bigcap은 분배법칙이 성립하므로 \\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에 의해 공집합 혹은 무한집합이므로, 그 합집합 또한 공집합 혹은 무한집합이 된다. 하지만 \\{1.-1\\}은 공집합도 무한집합도 아니므로 모순이 발생한다. 따라서 소수의 개수는 무한하다.
정수 m \\geq 2에 대하여 \\text{NM}(m) = (1 + m\\mathbb{Z}) \\cup (2 + m\\mathbb{Z}) \\cup \\cdots \\cup ((m-1) + m\\mathbb{Z})라 정의한다, \\text{NM}(m)은 m으로 나누어 떨어지지 않는 정수의 집합이다.
Claim 유한한 개수의 AP의 교집합은 공집합이거나 무한집합이다.
Proof AP들을 r_i+m_i\\mathbb{Z}\\ (1 \\leq i \\leq n)라 하자. \\displaystyle \\bigcap_{i=1}^n \\left( r_i + m_i \\mathbb{Z} \\right)가 공집합이면 증명이 끝난다. 공집합이 아니어서 원소 x가 존재한다면 x와 \\text{mod}\\ m_1m_2 \\cdots m_n에 대하여 합동인 모든 정수들이 \\displaystyle \\bigcap_{i=1}^n \\left( r_i + m_i \\mathbb{Z} \\right)의 원소가 되므로 \\displaystyle \\bigcap_{i=1}^n \\left( r_i + m_i \\mathbb{Z} \\right)는 무한집합이 된다. 따라서 증명이 끝났다.
Theorem 소수의 개수는 무한하다.
Proof 소수의 개수가 유한하여 p_1,\\ p_2,\\ \\cdots ,\\ p_k가 있다고 가정하자. 그리고 \\displaystyle\\bigcap_{i=1}^{k} \\text{NM}(p_i)를 생각해보자. \\displaystyle\\bigcap_{i=1}^{k} \\text{NM}(p_i)의 원소는 모든 p_i에 대해 나누어 떨어지지 않아야 하므로 \\bigcap_{i=1}^{k} \\text{NM}(p_i)= \\{1,-1\\}이 된다. 하지만 \\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]이고, \\bigcup과 \\bigcap은 분배법칙이 성립하므로 \\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에 의해 공집합 혹은 무한집합이므로, 그 합집합 또한 공집합 혹은 무한집합이 된다. 하지만 \\{1.-1\\}은 공집합도 무한집합도 아니므로 모순이 발생한다. 따라서 소수의 개수는 무한하다.
1.3. 증명 3 ✎ ⊖
\\mathbb{P}가 모든 소수의 집합이라고 하자. \\mathbb{P}가 유한집합이라고 가정하면 |\\mathbb{P}|=n이라 할 때 \\mathbb{P}=\\{p_1, p_2, \\cdots, p_n\\}이라고 쓸 수 있다. N=p_1 p_2 \\cdots p_n + 1이라고 하면 N\\not\\equiv 0 \\ (\\text{mod} \\ p_i)\\ (i\\in \\mathbb{N}, 1\\leq i \\leq n)이다.
따라서 N은 어느 소수로도 나누어지지 않으므로, N이 소수이거나 또는 N을 나누는 \\mathbb{P}에 속하지 않는 소수가 존재하므로 \\mathbb{P}가 모든 소수의 집합이라는 데 모순이다. 따라서 \\mathbb{P}는 무한집합이다.
따라서 N은 어느 소수로도 나누어지지 않으므로, N이 소수이거나 또는 N을 나누는 \\mathbb{P}에 속하지 않는 소수가 존재하므로 \\mathbb{P}가 모든 소수의 집합이라는 데 모순이다. 따라서 \\mathbb{P}는 무한집합이다.
2. 소수 정리 ✎ ⊖
소수 정리는 소수들의 분포를 잘 알려주는 정리로,
가 된다는 정리이다.
\\lim_{x\\to \\infty}\\frac{\\pi(x)\\ln{x}}{x}=1
가 된다는 정리이다.
