Prime Number / 素數
1과 자기 자신만을 약수로 가지는 1보다 큰 자연수를 말한다.
수론에서 가장 기본적이면서도 가장 중요한 개념 중 하나다. 모든 자연수는 소수들의 곱으로 표현할 수 있기 때문에, 소수는 자연수의 기본 단위라고 할 수 있다. 원소 주기율표의 수학 버전
개요[편집 / 원본 편집]
소수는 1보다 큰 자연수 중에서 1과 자기 자신으로만 나누어떨어지는 수를 의미한다. 예를 들어 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... 같은 수들이 모두 소수다.
반대로 1과 자기 자신 외에 다른 약수를 가지는 수는 합성수라고 한다. 4, 6, 8, 9, 10 같은 수들이 합성수다.
소수가 중요한 이유는 산술의 기본 정리 때문이다. 1보다 큰 모든 자연수는 소수들의 곱으로 유일하게 표현할 수 있다. 즉, 소수는 자연수를 구성하는 가장 기본적인 빌딩 블록이라고 할 수 있다.
정의[편집 / 원본 편집]
자연수 [math]\displaystyle{ p \gt 1 }[/math]에 대해, [math]\displaystyle{ p }[/math]의 약수가 1과 [math]\displaystyle{ p }[/math] 자기 자신뿐일 때, [math]\displaystyle{ p }[/math]를 소수라고 한다.
동치 정의로는 다음과 같은 것들이 있다:
- [math]\displaystyle{ p \gt 1 }[/math]이고, [math]\displaystyle{ 1 \lt a \lt p }[/math]인 자연수 [math]\displaystyle{ a }[/math]가 [math]\displaystyle{ p }[/math]를 나누지 못할 때
- [math]\displaystyle{ p \gt 1 }[/math]이고, 약수가 정확히 2개일 때
- [math]\displaystyle{ p \gt 1 }[/math]이고, [math]\displaystyle{ p = ab }[/math]라고 표현할 때 [math]\displaystyle{ a = 1 }[/math] 또는 [math]\displaystyle{ b = 1 }[/math]일 때
특징[편집 / 원본 편집]
1은 소수가 아니다[편집 / 원본 편집]
1은 소수가 아니다. 이것은 매우 중요한 사실이다.
과거에는 1을 소수로 취급하기도 했지만, 현대 수학에서는 1을 소수에서 제외한다. 그 이유는 다음과 같다:
- 산술의 기본 정리의 유일성이 깨진다. 만약 1을 소수로 치면 [math]\displaystyle{ 6 = 2 \times 3 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3 = \cdots }[/math]처럼 무한히 많은 방법으로 소인수분해할 수 있게 된다.
- 대부분의 정리에서 "1을 제외한 소수"라고 매번 언급해야 한다.
귀찮잖아 - 소수에 관한 많은 정리와 공식이 1을 포함하면 성립하지 않는다.
따라서 소수의 정의에 "[math]\displaystyle{ p \gt 1 }[/math]"이라는 조건이 반드시 들어간다.
무한성[편집 / 원본 편집]
소수는 무한히 많다. 이는 유클리드가 기원전 300년경에 증명한 정리다.
증명은 놀랍도록 간단하고 우아하다:
- 소수가 유한개라고 가정하자. 그 소수들을 [math]\displaystyle{ p_1, p_2, \ldots, p_n }[/math]이라고 하자.
- [math]\displaystyle{ N = p_1 \times p_2 \times \cdots \times p_n + 1 }[/math]이라는 수를 만들자.
- [math]\displaystyle{ N }[/math]은 모든 소수 [math]\displaystyle{ p_i }[/math]로 나눈 나머지가 1이므로, 어떤 소수로도 나누어떨어지지 않는다.
- 그러면 [math]\displaystyle{ N }[/math] 자체가 소수이거나, [math]\displaystyle{ N }[/math]을 나누는 새로운 소수가 존재한다.
- 어느 쪽이든 처음 가정에 모순이다. 따라서 소수는 무한히 많다. ∎
2000년 넘게 현역인 증명
가장 작은 소수[편집 / 원본 편집]
가장 작은 소수는 2다. 그리고 2는 유일한 짝수 소수이기도 하다.
2를 제외한 모든 짝수는 2로 나누어떨어지므로 합성수다. 따라서 3 이상의 모든 소수는 홀수다.
2가 유일한 짝수 소수라는 점은 많은 정리와 문제에서 예외 케이스로 다뤄진다. 2는 항상 특별 취급
소수의 분포[편집 / 원본 편집]
소수는 불규칙하게 나타나지만, 그 분포에는 일정한 패턴이 있다.
소수 정리(Prime Number Theorem)에 의하면, [math]\displaystyle{ n }[/math] 이하의 소수 개수 [math]\displaystyle{ \pi(n) }[/math]은 다음과 같이 근사할 수 있다:
[math]\displaystyle{ \pi(n) \sim \frac{n}{\ln n} }[/math]
이는 [math]\displaystyle{ n }[/math]이 커질수록 소수의 밀도가 점점 줄어든다는 의미다. 예를 들어:
- 100 이하: 25개 (25%)
- 1,000 이하: 168개 (16.8%)
- 10,000 이하: 1,229개 (12.29%)
- 100,000 이하: 9,592개 (9.592%)
평균적으로 [math]\displaystyle{ n }[/math] 근처에서 다음 소수까지의 간격은 약 [math]\displaystyle{ \ln n }[/math] 정도다.
예시[편집 / 원본 편집]
작은 소수들[편집 / 원본 편집]
100 이하의 소수는 다음과 같다:
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
총 25개다. 이 중에서 2만 짝수이고 나머지는 모두 홀수다.
큰 소수[편집 / 원본 편집]
소수 판별법[편집 / 원본 편집]
시행 착오법[편집 / 원본 편집]
가장 단순한 방법은 2부터 [math]\displaystyle{ n-1 }[/math]까지 모든 수로 나눠보는 것이다. 하지만 이는 너무 느리다.
개선된 방법은 2부터 [math]\displaystyle{ \sqrt{n} }[/math]까지만 확인하는 것이다. 왜냐하면 [math]\displaystyle{ n = a \times b }[/math]일 때, [math]\displaystyle{ a }[/math]와 [math]\displaystyle{ b }[/math] 중 적어도 하나는 [math]\displaystyle{ \sqrt{n} }[/math] 이하이기 때문이다.
에라토스테네스의 체[편집 / 원본 편집]
에라토스테네스의 체는 일정 범위 내의 모든 소수를 찾는 효율적인 알고리즘이다.
알고리즘:
- 2부터 [math]\displaystyle{ n }[/math]까지의 모든 수를 나열한다.
- 2는 소수이므로 남기고, 2의 배수를 모두 지운다.
- 다음 남은 수(3)는 소수이므로 남기고, 3의 배수를 모두 지운다.
- 이를 [math]\displaystyle{ \sqrt{n} }[/math]까지 반복한다.
- 남은 수들이 모두 소수다.
시간 복잡도는 [math]\displaystyle{ O(n \log \log n) }[/math]으로 매우 효율적이다.
밀러-라빈 소수 판별법[편집 / 원본 편집]
밀러-라빈 소수 판별법은 확률적 알고리즘으로, 매우 빠르게 소수 여부를 판별할 수 있다. RSA 암호 같은 암호학에서 큰 소수를 생성할 때 주로 사용된다.
완벽하게 정확하지는 않지만, 반복 횟수를 늘리면 오류 확률을 임의로 낮출 수 있다. 실용적으로는 거의 100% 정확하다
AKS 소수 판별법[편집 / 원본 편집]
AKS 소수 판별법은 2002년에 발견된 결정론적 다항 시간 알고리즘이다. 이론적으로 매우 중요하지만, 실제로는 밀러-라빈보다 느려서 잘 사용되지 않는다.
그래도 "소수 판별은 P 문제다"라는 것을 증명했다는 점에서 역사적 의의가 크다.
특수한 소수들[편집 / 원본 편집]
메르센 소수[편집 / 원본 편집]
메르센 소수(Mersenne prime)는 [math]\displaystyle{ 2^p - 1 }[/math] 꼴의 소수를 말한다. (단, [math]\displaystyle{ p }[/math]도 소수여야 함)
예시:
- [math]\displaystyle{ 2^2 - 1 = 3 }[/math]
- [math]\displaystyle{ 2^3 - 1 = 7 }[/math]
- [math]\displaystyle{ 2^5 - 1 = 31 }[/math]
- [math]\displaystyle{ 2^7 - 1 = 127 }[/math]
메르센 소수는 완전수와 밀접한 관련이 있다. 짝수 완전수는 모두 [math]\displaystyle{ 2^{p-1}(2^p - 1) }[/math] 꼴이며, 여기서 [math]\displaystyle{ 2^p - 1 }[/math]은 메르센 소수다.
알려진 가장 큰 소수들은 대부분 메르센 소수다. 이들은 특별한 구조 덕분에 소수 판별이 비교적 쉽기 때문이다.
쌍둥이 소수[편집 / 원본 편집]
쌍둥이 소수(Twin prime)는 차이가 2인 소수 쌍을 말한다.
예시: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73)...
쌍둥이 소수가 무한히 많은지는 아직 증명되지 않았다. 이를 쌍둥이 소수 추측이라고 하며, 수론의 7대 난제 중 하나다. 언젠가는 풀리겠지
페르마 소수[편집 / 원본 편집]
페르마 소수(Fermat prime)는 [math]\displaystyle{ 2^{2^n} + 1 }[/math] 꼴의 소수를 말한다.
알려진 페르마 소수는 단 5개뿐이다:
- [math]\displaystyle{ F_0 = 2^{2^0} + 1 = 3 }[/math]
- [math]\displaystyle{ F_1 = 2^{2^1} + 1 = 5 }[/math]
- [math]\displaystyle{ F_2 = 2^{2^2} + 1 = 17 }[/math]
- [math]\displaystyle{ F_3 = 2^{2^3} + 1 = 257 }[/math]
- [math]\displaystyle{ F_4 = 2^{2^4} + 1 = 65537 }[/math]
페르마는 모든 [math]\displaystyle{ F_n }[/math]이 소수일 것이라고 추측했지만, 오일러가 [math]\displaystyle{ F_5 = 641 \times 6700417 }[/math]임을 보이며 반례를 찾았다. 페르마의 착각
페르마 소수는 정다각형의 작도와 관련이 있다. 정[math]\displaystyle{ n }[/math]각형이 자와 컴퍼스로 작도 가능한 필요충분조건은 [math]\displaystyle{ n = 2^k p_1 p_2 \cdots p_m }[/math] (단, [math]\displaystyle{ p_i }[/math]는 서로 다른 페르마 소수)이다.
소피 제르맹 소수[편집 / 원본 편집]
소피 제르맹 소수는 소수 [math]\displaystyle{ p }[/math]에 대해 [math]\displaystyle{ 2p + 1 }[/math]도 소수인 경우를 말한다.
예시: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131...
이 소수들은 페르마의 마지막 정리 증명 과정에서 중요한 역할을 했다.
회문 소수[편집 / 원본 편집]
회문 소수는 앞뒤로 읽어도 같은 소수를 말한다.
예시: 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929...
10진법 외에 다른 진법에서의 회문 소수도 연구된다.
순환 소수[편집 / 원본 편집]
순환 소수(Circular prime)는 자릿수를 회전시켜도 모두 소수인 수를 말한다.
예시:
- 2, 3, 5, 7 (한 자리)
- 11, 13, 17, 31, 37, 71, 73, 79, 97 (두 자리)
- 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991 (세 자리)
100만 이하에는 55개의 순환 소수가 있다.
응용[편집 / 원본 편집]
암호학[편집 / 원본 편집]
현대 암호학에서 소수는 필수적이다. 특히 RSA 암호는 큰 수의 소인수분해가 어렵다는 사실을 이용한다.
RSA의 기본 원리:
- 두 개의 큰 소수 [math]\displaystyle{ p, q }[/math]를 선택한다. (보통 각각 1024비트 이상)
- [math]\displaystyle{ n = p \times q }[/math]를 공개키로 사용한다.
- [math]\displaystyle{ n }[/math]을 알아도 [math]\displaystyle{ p, q }[/math]를 찾기는 매우 어렵다.
- 이 어려움이 암호의 안전성을 보장한다.
만약 효율적인 소인수분해 알고리즘이 발견되면 RSA 암호는 무용지물이 된다. 양자컴퓨터가 그럴 수도
해시 테이블[편집 / 원본 편집]
해시 테이블의 크기를 정할 때 소수를 사용하면 해시 충돌을 줄일 수 있다. 특히 선형 탐사나 이중 해싱을 사용할 때 효과적이다.
난수 생성[편집 / 원본 편집]
의사 난수 생성기에서 소수가 자주 사용된다. 선형 합동 생성기(LCG)에서 모듈러스로 큰 소수를 사용하면 주기가 길어진다.
매미의 생애주기[편집 / 원본 편집]
북미의 주기성 매미는 13년 또는 17년 주기로 나타나는데, 이 두 수는 모두 소수다. 이는 포식자의 생애주기와 겹치는 것을 최소화하기 위한 진화적 전략으로 추정된다. 자연도 수학을 안다
미해결 문제[편집 / 원본 편집]
골드바흐의 추측[편집 / 원본 편집]
골드바흐의 추측(Goldbach's conjecture): 2보다 큰 모든 짝수는 두 소수의 합으로 표현할 수 있다.
예시:
- [math]\displaystyle{ 4 = 2 + 2 }[/math]
- [math]\displaystyle{ 6 = 3 + 3 }[/math]
- [math]\displaystyle{ 8 = 3 + 5 }[/math]
- [math]\displaystyle{ 10 = 3 + 7 = 5 + 5 }[/math]
1742년에 제시되었지만 아직까지 증명되지 않았다. [math]\displaystyle{ 4 \times 10^{18} }[/math]까지는 컴퓨터로 확인되었다.
쌍둥이 소수 추측[편집 / 원본 편집]
쌍둥이 소수 추측(Twin prime conjecture): 쌍둥이 소수가 무한히 많다.
2013년 장이탕이 "차이가 7000만 이하인 소수 쌍이 무한히 많다"는 것을 증명했고, 이후 이 차이는 246까지 줄어들었다. 하지만 2로 줄이는 것은 여전히 미해결 과제다.
리만 가설[편집 / 원본 편집]
리만 가설(Riemann hypothesis)은 소수의 분포와 관련된 가장 중요한 미해결 문제다. 100만 달러의 상금이 걸려 있는 밀레니엄 문제 중 하나다.
리만 제타 함수 [math]\displaystyle{ \zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s} }[/math]의 비자명한 영점이 모두 [math]\displaystyle{ \text{Re}(s) = \frac{1}{2} }[/math] 선 위에 있다는 추측이다.
이게 증명되면 소수의 분포에 대한 매우 정확한 정보를 얻을 수 있다. 언제 풀릴지는 모르겠지만
ABC 추측[편집 / 원본 편집]
역사[편집 / 원본 편집]
여담[편집 / 원본 편집]
- 소수를 영어로 prime number라고 하는데, prime은 "첫 번째, 주요한"이라는 뜻이다. 실제로 소수는 모든 자연수의 기본이 되므로 적절한 이름이다.
- 구글의 첫 IPO 공모가는 85달러가 아니라 정확히 [math]\displaystyle{ 2^{2^5} - 1 = 2,147,483,647 }[/math]센트였다... 는 농담이고, 실제로는 85달러였다. 하지만 구글은 여러 곳에서 소수를 활용하는 것으로 유명하다.
- 소수의 한자 표기는 素數인데, 素는 "본래의, 기본적인"이라는 뜻이다. 중국어와 일본어에서도 같은 표기를 사용한다.
- 1이 소수가 아니라는 사실을 받아들이지 못하는 사람들이 의외로 많다. "1과 자기 자신으로만 나누어떨어지잖아!"라고 항변하지만, 정의에 "[math]\displaystyle{ p \gt 1 }[/math]"이라는 조건이 있다는 것을 잊으면 안 된다.
- 시카다 문제에서 소수의 중요성을 엿볼 수 있다. 13년, 17년처럼 소수 주기를 가지면 포식자와 주기가 겹칠 확률이 최소화된다. 예를 들어 13과 17의 최소공배수는 221이지만, 12와 18의 최소공배수는 36에 불과하다.
- [math]\displaystyle{ p }[/math]가 홀수 소수일 때, [math]\displaystyle{ \frac{1}{p} }[/math]를 소수로 나타내면 순환마디가 나타난다. 예를 들어 [math]\displaystyle{ \frac{1}{7} = 0.\overline{142857} }[/math]이다. 이 순환마디의 길이는 최대 [math]\displaystyle{ p-1 }[/math]이다.
- 2의 거듭제곱에서 1을 뺀 수 중 소수가 많다는 것은 흥미롭지만, 2의 거듭제곱에 1을 더한 수는 대부분 합성수다. [math]\displaystyle{ 2^{2^n} + 1 }[/math] 꼴의 페르마 소수는 5개만 알려져 있다.