소수 (수론)

0과 1사이의, 또는 소수점으로 나타낸 작은 수(小數)에 관한 내용은 소수 (기수법) 문서를 읽어 주세요.

정의

소수(素數, 발음: /소쑤/)는 1보다 큰 자연수 중에서 약수가 1과 자기 자신뿐인 수를 말한다. 즉, 약수개 두 개인 수. 1은 소수의 정의에 포함되지 않으며, 이는 산술의 기본 정리를 만족하게 하기 위해서이다. 1도 소수도 아닌 수는 합성수라 불린다.

어떤 자연수를 소수인 약수들의 곱으로 나타내는 것을 소인수분해라 하며, 자연수의 소인수분해는 반드시 유일하게 존재한다. (산술의 기본 정리)

정수에서는 0이나 ±1이 아닌 정수 중에서 양의 약수가 1과 자기 자신뿐인 수로 정의한다.

찾는 방법

소수를 찾는 방법으로는 중학교 교과서에서 소개되는 에라토스테네스의 체가 유명하다. 예시를 통해 알아보자.

1부터 120까지의 자연수 중에 소수인 것을 모두 구해보자.

• 먼저 자연수를 나눌 만한 소수를 찾는다. 이때 소수 p는 [math]\displaystyle{ p\le \lfloor\sqrt{120}\rfloor }[/math]을 만족하는 것이면 충분하다. 이때 부등식을 만족하는 소수는 2, 3, 5, 7이다.
• 1은 소수가 아닌 걸 아니까 소거한다.
• 2부터 120까지의 수 중에 2의 배수인 것을 모두 소거한다.
• 남은 수 중에 3의 배수인 것을 모두 제거한다.
• 남은 수 중에 5의 배수인 것을 모두 제거한다.
• 남은 수 중에 7의 배수인 것을 모두 제거한다.
• 소거 과정을 거치고 남은 것들은 모두 소수다. 어때요, 정말 쉽죠?

이 방법은 소수를 찾는 방법 중 가장 단순하고 동시에 비효율적인 방법이다. 현대에는 소수 정리와 같은 소수를 찾는데 아주 아주 아주 조금 효율적인 수학 정리들이 존재한다.

소수의 개수

소수의 개수는 무한함이 알려져 있는데, 이 사실은 유클리드가 처음 증명했다. 또한 디리클레 등차수열 정리에 따르면 서로소인 두 양의 정수 [math]\displaystyle{ a,b }[/math]에 대해 [math]\displaystyle{ an+b }[/math] (단, [math]\displaystyle{ n }[/math]은 음이 아닌 정수) 꼴의 소수도 무한히 많다.

증명

유클리드의 증명

소수의 개수가 유한하다고 가정하자. 그러면 유한한 소수를 [math]\displaystyle{ p_1,p_2,\cdots, p_n }[/math]으로 둘 수 있다. 이제 [math]\displaystyle{ N }[/math]을

[math]\displaystyle{ N=p_1p_2\cdots p_n + 1 }[/math]

로 정의하자. 그러면 [math]\displaystyle{ N \ge 2 }[/math]이므로 [math]\displaystyle{ N }[/math]의 소인수 [math]\displaystyle{ p }[/math]가 존재한다. 즉, [math]\displaystyle{ p\mid p_1p_2\cdots p_n+1 }[/math]이고 [math]\displaystyle{ p\mid p_1p_2\cdots p_n }[/math]이므로 [math]\displaystyle{ p\mid 1 }[/math]이 되어 모순이다. 따라서 소수의 개수는 무한하다.

소수 계량 함수

이와 관련한 내용은 소수 계량 함수, 소수 정리에서 볼 수 있습니다.

실수 [math]\displaystyle{ x\gt 0 }[/math]에 대해 [math]\displaystyle{ x }[/math]보다 작거나 같은 소수의 개수를 [math]\displaystyle{ \pi(x) }[/math]라고 하자. 이때 [math]\displaystyle{ \pi: \mathbb{R}_{\gt 0} \to \mathbb{N} }[/math]를 소수 계량 함수라고 한다. 이때 다음 식이 성립한다는 것이 알려져 있다.

[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)에서는 모든 소수는 기약수이다. 그러나 그 역은 일반적으로는 참이 아니며, 유일 인수분해 정역(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]임을 쉽게 보일 수 있다.

1. [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. 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는 기약수이다.
3. 비슷한 방법으로 [math]\displaystyle{ 3,\,1\pm\sqrt{-5} }[/math]가 기약수라는 사실을 보일 수 있다.
4. 이제, [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가 소수가 아닐 수도 있다. 이는 다른 소수들도 마찬가지라 소수가 소수가 아닌(...) 경우가 존재한다. 이처럼 어떤 수가 소수(혹은 기약수)라고 하려면 어떤 환에서 하는 얘기인지를 언급해 주어야 명확하다. 예를 들어 앞서 언급한 ‘2는 소수’라는 사실은 정수환을 염두하고 이야기한 것이다. 그런데 이렇게 의미의 불명확함이 있을 때마다 ‘정수환에서의 소수’, ‘정수 중의 소수’라고 하기는 상당히 귀찮기 때문에 일상적으로 그냥 ‘소수’라 할 때는 정수 중의 소수를 이야기하는 것으로 암묵적으로 합의하고 있다.

소아이디얼(Prime ideal)

소수의 또 다른 일반화로 소아이디얼이 있다.

[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 = 2¹⁶+1 = 2²⁴+1: 현재까지 알려진 가장 큰 페르마 소수로서, 컴퓨터에서 65537제곱을 하기가 쉽다는 특성 때문에 암호론 등에서 자주 등장한다.
• 메르센 소수: [math]\displaystyle{ 2^p-1 }[/math] 꼴의 소수. 이때 [math]\displaystyle{ p }[/math]는 소수다. 2016년 2월 현재 49개가 알려져 있으며, 가장 큰 메르센 소수는 2016년에 발견된 [math]\displaystyle{ 2^{74207281}-1 }[/math]이다.
• 쌍둥이소수: 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ p+2 }[/math]가 소수이면 [math]\displaystyle{ p }[/math]와 [math]\displaystyle{ p+2 }[/math]를 쌍둥이소수라고 한다.
• 제르멩 소수: 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ 2p+1 }[/math]이 소수이면 [math]\displaystyle{ p }[/math]를 제르멩 소수라고 한다.