편집 요약 없음 |
편집 요약 없음 |
||
24번째 줄: | 24번째 줄: | ||
이 방법은 소수를 찾는 방법 중 가장 단순하고 동시에 비효율적인 방법이다. 현대에는 소수 정리와 같은 소수를 찾는데 {{ㅊ|아주 아주 아주}} 조금 효율적인 수학 정리들이 존재한다. | 이 방법은 소수를 찾는 방법 중 가장 단순하고 동시에 비효율적인 방법이다. 현대에는 소수 정리와 같은 소수를 찾는데 {{ㅊ|아주 아주 아주}} 조금 효율적인 수학 정리들이 존재한다. | ||
== 소수의 개수 == | |||
소수의 개수는 무한함이 알려져 있는데, 이 사실은 [[유클리드]]가 처음 증명했다. 또한 [[디리클레 등차수열 정리]]에 따르면 [[서로소]]인 두 양의 정수 \(a,b\)에 대해 \(an+b\) (단, \(n\)은 음이 아닌 정수) 꼴의 소수도 무한히 많다. | |||
=== 증명 === | |||
==== 유클리드의 증명 ==== | |||
소수의 개수가 유한하다고 가정하자. 그러면 유한한 소수를 \(p_1,p_2,\cdots, p_n\)으로 둘 수 있다. 이제 \(N\)을 | |||
: <math>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>\lim_{x\to \infty}\frac{\pi(x)\ln x}{x}=1</math> | |||
==소수의 일반화== | ==소수의 일반화== |
2015년 11월 9일 (월) 01:56 판
정의
소수(素數, 발음: /소쑤/)는 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 }[/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제곱을 하기가 쉽다는 특성 때문에 암호론 등에서 자주 등장한다.
각주
- ↑ 일반적으로, 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].