정의
소수(素數, 발음: /소쑤/)는 1보다 큰 자연수 중에서 약수가 1과 자기 자신뿐인 수를 말한다. 즉, 약수개 두 개인 수. 중요한 것은 1은 소수가 아니라 중성수라 불린다. 1도 소수도 아닌 수는 합성수라 불린다.
어떤 자연수를 소수인 약수들의 곱으로 나타내는 것을 소인수분해 라 하며, 자연수의 소인수분해는 반드시 존재하며, 유일하다.
정수에서는 0이나 ±1이 아닌 정수 중에서 양의 약수가 1과 자기 자신뿐인 수로 정의한다.
찾는 방법
소수를 찾는 방법으로는 중학교 교과서에서 소개되는 에라토스테네스의 체가 유명하다. 예시를 통해 알아보자.
1부터 120까지의 자연수 중에 소수인 것을 모두 구해보자.
- 먼저 자연수를 나눌 만한 소수를 찾는다. 이때 소수 p는 [math]\displaystyle{ p\le \lfloor\sqrt{120}\rfloor }[/math]을 만족하는 것이면 충분하다.[1] 이때 부등식을 만족하는 소수는 2, 3, 5, 7이다.
- 1은 소수가 아닌 걸 아니까 소거한다.
- 2부터 120까지의 수 중에 2의 배수인 것을 모두 소거한다.
- 남은 수 중에 3의 배수인 것을 모두 제거한다.
- 남은 수 중에 5의 배수인 것을 모두 제거한다.
- 남은 수 중에 7의 배수인 것을 모두 제거한다.
- 소거 과정을 거치고 남은 것들은 모두 소수다.
어때요, 정말 쉽죠?
이 방법은 소수를 찾는 방법 중 가장 단순하고 동시에 비효율적인 방법이다. 현대에는 소수 정리와 같은 소수를 찾는데 아주 아주 아주 조금 효율적인 수학 정리들이 존재한다.
소수의 개수
소수의 개수는 무한함이 알려져 있는데, 이 사실은 유클리드가 처음 증명했다. 또한 디리클레 등차수열 정리에 따르면 서로소인 두 양의 정수 \(a,b\)에 대해 \(an+b\) (단, \(n\)은 음이 아닌 정수) 꼴의 소수도 무한히 많다.
증명
유클리드의 증명
소수의 개수가 유한하다고 가정하자. 그러면 유한한 소수를 \(p_1,p_2,\cdots, p_n\)으로 둘 수 있다. 이제 \(N\)을
- [math]\displaystyle{ N=p_1p_2\cdots p_n + 1 }[/math]
로 정의하자. 그러면 \(N \ge 2\)이므로 \(N\)의 소인수 \(p\)가 존재한다. 즉, \(p\mid p_1p_2\cdots p_n+1\)이고 \(p\mid p_1p_2\cdots p_n\)이므로 \(p\mid 1\)이 되어 모순이다. 따라서 소수의 개수는 무한하다.
소수 계량 함수
실수 \(x>0\)에 대해 \(x\)보다 작거나 같은 소수의 개수를 \(\pi(x)\)라고 하자. 이때 \(\pi: \mathbb{R}_{>0} \to \mathbb{N}\)를 소수 계량 함수라고 한다. 이때 다음 식이 성립한다는 것이 알려져 있다.
- [math]\displaystyle{ \lim_{x\to \infty}\frac{\pi(x)\ln x}{x}=1 }[/math]
소수의 일반화
소수의 일반화로 기약수가 있다.
앞서 자연수 영역에서의 소수를 ‘1보다 큰 자연수 중에서 약수가 1과 자신뿐인 수’로 정의하였으나, 사실은 다음 두 정의가 혼용되고 있었다.
- [math]\displaystyle{ p\gt 1 }[/math]이고 [math]\displaystyle{ ab=p }[/math]이면 [math]\displaystyle{ a=1 }[/math] 또는 [math]\displaystyle{ b=1 }[/math].
- [math]\displaystyle{ p\gt 1 }[/math]이고 [math]\displaystyle{ p\mid ab }[/math]이면 [math]\displaystyle{ p\mid a }[/math] 또는 [math]\displaystyle{ p\mid b }[/math].
- ([math]\displaystyle{ a\mid b }[/math]는 [math]\displaystyle{ b }[/math]가 [math]\displaystyle{ a }[/math]로 나누어 떨어진다는 뜻.)
이 두 정의는 자연수의 소인수분해를 생각하면 동치임이 명백하다. 그러나 다항식에서 비슷한 역할을 하는 기약다항식 등을 연구하면서, 수학자들은 두 정의가 일반적으로는 동치가 아님을 알게 되었다. 따라서 다음과 같이 구분하게 되었다.
[math]\displaystyle{ R }[/math]이 1을 갖는 가환환일 때, [math]\displaystyle{ p \in R }[/math]에 대하여
- [math]\displaystyle{ p }[/math]가 non-zero, non-unit이고 [math]\displaystyle{ a }[/math], [math]\displaystyle{ b \in R }[/math]에 대해 [math]\displaystyle{ ab=p }[/math]이면 [math]\displaystyle{ a \in R^* }[/math] 또는 [math]\displaystyle{ b \in R^* }[/math]이면 [math]\displaystyle{ p }[/math]는 기약수(irreducible element).
- [math]\displaystyle{ p }[/math]가 non-zero, non-unit이고 [[math]\displaystyle{ a }[/math], [math]\displaystyle{ b \in R }[/math]에 대해 [math]\displaystyle{ p\mid ab }[/math]이면 [math]\displaystyle{ p\mid a }[/math] 또는 [math]\displaystyle{ p\mid b }[/math]]이면 [math]\displaystyle{ p }[/math]는 소수(prime element).
정역(Integral domain)에서는 모든 소수는 기약수이다.[2] 그러나 그 역은 일반적으로는 참이 아니며, 유일 인수분해 정역(Unique Factorization Domain)에서는 모든 기약수는 소수임을 증명할 수 있다.
기약수가 항상 소수가 아니라는 사실에서 일반상식을 깨는 수학적 사실을 하나 이끌어 낼 수 있다.
- [math]\displaystyle{ R=\mathbb{Z}\left[\sqrt{-5}\right] }[/math]의 원소 6을 생각하자. 먼저, [math]\displaystyle{ 6=2\cdot3=\left(1+\sqrt{-5}\right)\left(1-\sqrt{-5}\right) }[/math]임을 쉽게 보일 수 있다.
- [math]\displaystyle{ R^* }[/math]의 원소를 구해보자. [math]\displaystyle{ \left(a+b\sqrt{-5}\right)\left(c+\sqrt{-5}\right)=1 }[/math]에서 양변에 켤레 복소수를 곱해주면, [math]\displaystyle{ \left(a^2+5b^2\right)\left(c^2+5d^2\right)=1 }[/math]. [math]\displaystyle{ a,\,b,\,c,\,d\in\mathbb{Z} }[/math]이므로, [math]\displaystyle{ b=d=0 }[/math]이고, [math]\displaystyle{ a=\pm1,\,c=\pm1 }[/math]임을 알 수 있다. 즉, [math]\displaystyle{ R^*=\left\{\pm1\right\} }[/math]
- 2가 기약수라는 사실을 보이자. [math]\displaystyle{ 2=\left(a+b\sqrt{-5}\right)\left(c+\sqrt{-5}\right) }[/math]라 가정하자. 양변에 켤레 복소수를 곱해주면, [math]\displaystyle{ \left(a^2+5b^2\right)\left(c^2+5d^2\right)=4 }[/math]이다. 그런데 [math]\displaystyle{ a,\,b,\,c,\,d\in\mathbb{Z} }[/math]이므로, [math]\displaystyle{ b=d=0 }[/math]이고, [math]\displaystyle{ 4=a^2c^2 }[/math]이다. 따라서, [math]\displaystyle{ 2=\pm ac }[/math]이고, 이는 곧 [math]\displaystyle{ a }[/math]나 [math]\displaystyle{ c }[/math]중 하나는 [math]\displaystyle{ \pm1 }[/math]임을 의미한다. 따라서, 2는 기약수이다.
- 비슷한 방법으로 [math]\displaystyle{ 3,\,1\pm\sqrt{-5} }[/math]가 기약수라는 사실을 보일 수 있다.
- 이제, [math]\displaystyle{ 2\mid2\cdot3=6=\left(1+\sqrt{-5}\right)\left(1-\sqrt{-5}\right) }[/math]이다. 그런데, [math]\displaystyle{ 2\notin R^* }[/math]이고, [math]\displaystyle{ 1\pm\sqrt{-5} }[/math]는 기약수이므로, [math]\displaystyle{ 2\nmid1\pm\sqrt{-5} }[/math]이다. 따라서, 2는 소수가 아니다.
뭐라고요?????
학교에서 2는 짝수인 소수라고 수도 없이 들었을테지만, 위와같이 특정한 환에서는 2가 소수가 아닐 수도 있다.[3] 이는 다른 소수들도 마찬가지라 소수가 소수가 아닌(...) 경우가 존재한다. 물론, 우리가 흔히 사용하는 실수 체계에서는 2가 소수이므로 걱정하지 말자.[4]
소수의 또 다른 일반화로 소아이디얼이 있다.
[math]\displaystyle{ R }[/math]이 1을 갖는 가환환일 때, [math]\displaystyle{ R }[/math]의 아이디얼(ideal) [math]\displaystyle{ I }[/math]에 대하여 [math]\displaystyle{ I \neq R }[/math]이고 [[math]\displaystyle{ a }[/math], [math]\displaystyle{ b \in R }[/math]에 대해 [math]\displaystyle{ ab \in I }[/math]이면 [math]\displaystyle{ a \in I }[/math] 또는 [math]\displaystyle{ b \in I }[/math]]이면 [math]\displaystyle{ I }[/math]는 소아이디얼(prime ideal)이라 한다. 약수와 배수 관계가 아이디얼의 포함관계에 대응된다는 점을 생각하면 위 정의가 소수에 관한 앞서의 정의와 상통함을 알 수 있다. 따라서 [math]\displaystyle{ p \neq 0 }[/math]일 때 [math]\displaystyle{ p }[/math]가 소수인 것과 [math]\displaystyle{ p }[/math]가 생성하는 아이디얼 [math]\displaystyle{ (p) }[/math]이 소 아이디얼인 것이 동치임은 자명하다.
주의할 점은 [math]\displaystyle{ R }[/math] 자신은 소아이디얼이라고 부르지 않는다는 것이다. 이는 1이 소수가 아닌 것과 마찬가지이다. 즉, 소 아이디얼의 정의에서 [math]\displaystyle{ I \neq R }[/math]이라는 조건은 [math]\displaystyle{ p }[/math]가 non-unit이라는 조건에 대응된다. 그러나 또 주의할 점은 [math]\displaystyle{ I }[/math]가 non-zero일 것은 요하지 않으므로, 영 아이디얼 0도 소아이디얼일 수 있다는 것이다. 따라서 앞서의 명제에서 [math]\displaystyle{ p \neq 0 }[/math]이라는 조건을 빼먹으면 곤란하다.
어떤 환에서 소인수분해가 유일하게 되지 않는다 하더라도, 즉 그 환이 유일 인수분해 정역(UFD)가 아니라 하더라도 그 환이 데데킨트 환이라면 모든 아이디얼은 소아이디얼들로 유일하게 소인수분해가 된다.
유명한 소수
- 2: 짝수인 유일한 소수.
- 691: 베르누이 수와 관련되어 있다는 지표가 된다.
- 65537 = 216+1 = 224+1: 현재까지 알려진 가장 큰 페르마 소수로서, 컴퓨터에서 65537제곱을 하기가 쉽다는 특성 때문에 암호론 등에서 자주 등장한다.
- 메르센 소수: [math]\displaystyle{ 2^p-1 }[/math] 꼴의 소수. 이때 \(p\)는 소수다. 2015년 11월 현재 48개가 알려져 있으며, 가장 큰 메르센 소수는 2013년에 발견된 \(2^{57885161}-1\)이다.
- 쌍둥이소수: 소수 \(p\)에 대해 [math]\displaystyle{ p+2 }[/math]가 소수이면 \(p\)와 \(p+2\)를 쌍둥이소수라고 한다.
- 제르멩 소수: 소수 \(p\)에 대해 [math]\displaystyle{ 2p+1 }[/math]이 소수이면 \(p\)를 제르멩 소수라고 한다.
각주
- ↑ 일반적으로, n이 합성수라면 [math]\displaystyle{ p\le \lfloor\sqrt{n}\rfloor }[/math]인 n의 소인수 p가 존재한다. 김응태·박승안. 『정수론』(제8판). 경문사. ISBN 9788961055956
- ↑ 증명: [math]\displaystyle{ ab=p }[/math]이면 [math]\displaystyle{ p\mid ab }[/math]이다. 예를 들어 [math]\displaystyle{ p\mid a }[/math]라 하면 어떤 [math]\displaystyle{ c \in R }[/math]에 대해 [math]\displaystyle{ pc=a }[/math]이고, 첫 식에 대입하여 [math]\displaystyle{ pcb=ab=p }[/math]를 얻는다. 양변에서 [math]\displaystyle{ p }[/math]를 소거하면 [math]\displaystyle{ cb=1 }[/math]이므로 [math]\displaystyle{ b \in R^* }[/math].
- ↑ [math]\displaystyle{ \mathbb{Z}\left[\sqrt{-5}\right] }[/math]는 UFD가 아니기 때문에 이게 가능하다.
- ↑ 이는 [math]\displaystyle{ \mathbb{R} }[/math]이 주 아이디얼 정역이기 때문이다. 좀 더 범위를 좁히면, 실수는 유클리드 정역이다.