소수(Prime number) 이야기
수학에서 소수란, 1보다 큰 자연수 들 중에서 1과 자기 자신으로만 나누어 떨어지는 수를 가리키는 말이다. 무수히 많은 소수들이 있다는 것은 기원전 300년 경 위대한 그리스 수학자 유클리드에 의해 증명되었다. 처음 몇 개의 소수들을 나열해 보자면
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,... 로 무수히 많이 있다.
소수에 대한 연구는 정수론에 많은 부분을 차지 하고 있다. 소수에 대해 많은 수학자들이 연구를 하였고, 아직도 몇 가지 기본적인 질문들을 해결하지 못한 것 들이 있다. 예를들어 리만 가설(Riemann hypothesis) 이라던지, 골드바흐 추론(Goldbach conjecture)등은 아직도 몇 세기 동안 해결되지 못한 것들이다. 소수의 빈도수 또한 정수론 학자들에게는 매우 인기있는 주제이기도 하다.
소수의 역사
이집트인들의 기록을 살펴보자면 그들이 소수에 대한 약간에 지식은 있었던 것으로 보인다. 예를들어 Rhind papyrus 에선, 여러가지 소수들과 합성수 들이 써져 있었다. 그러나 실질적으로 소수에 대한 연구가 시작된 것은 고대 그리스 부터였다. 유클리드 원론(기원전 300년)에선 몇 가지 기본적이고 중요한 증명들이 있는데 예를들면 소수의 무한성도 그 중 하나였다. 또한 유클리드는 메르센느 소수로 부터 어떻게 완전수를 만들 수 있는지도 보였다.
에라토스테네스(Eratosthenes)가 만든 에라토스테네스 체( Sieve of Eratosthenes )는 소수를 찾기에는 가장 간단한 방법이지만 현재 큰 소수를 찾는 컴퓨터는 이 알고리즘은 택하지 않았다. 그리스 이후 17세기까지 소수에 대한 연구는 큰 진보를 하지 않았으나 다음과 같은 사실이 발견되었다.
1640년 피에르 데 페르마 (Pierre de Fermat) 는 그의 페르마 소정리 (Fermat's little theorem) 를 발견하고 후에 라이프니치(Leibnitz)와 오일러(Euler)에 의해 증명되었다. 참고적으로 페르마 소정리의 특정 부분은 훨씬 전부터 중국에서도 알려져 있었다. 페르마는 n=4 일때 까지 해 본후 모든 22n + 1 꼴의 수는 소수일 것이라고 추측하였으나 (이들을 페르마 수 라 부른다)그 다음 페르마 수인 232+1 은, 오일러의 노력에 의해 641의 배수임을 보였다. 또한 오일러는 그 다음부터 모든 페르마 수들은 소수가 아님을 발견하였다.
프랑스의 수도사 마린 메르센느(Marin Mersenne) 은 2p - 1 꼴의 소수 ( p 는 소수 ) 를 살펴보았고 이는 나중에 영광스럽게도 메르센느 소수라는 이름이 붙었다.
오일러의 정수에 대한 연구는 소수에 대해 많은 결과를 낳았는데, 그는 다음 무한 급수 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + .... 가 발산함을 보이며 소수가 무한함을 오일러와 다른 방식으로 증명하였다. 게다가 오일러는 2p-1(2p-1) 의 수 ( 두번째 항이 메르센느 소수 ) 들이 모두 유일한 짝수 완전수 꼴 임을 보였다. 현재까지 홀수 완전수가 없음은 분명해 보이나 아직까지 증명은 되지 않았다.
그 후 19세기 초에, 르장드르( Legendre )와 가우스(Gauss) 는 독립적으로 x가 무한대로 증가할 때, 자연수 x 까지의 소수의 개수는 x/log(x) 에 접근함을 보였다. 1859년에 리만은 그의 논문서 제타 함수(zeta-function) 에 대한 아이디어를 남겼다. 그것을 통해서 소수정리를 증명 할 수 있었고, Hadamard 와 de la Vallée Poussin 에 의해 독립적으로 위 리만의 아이디어를 이용해 1896년 소수 정리를 증명하였다.
수학자들은 어떤 큰 수에 대해서 나누기 너무 오랜 시간이 걸리기 위해 짧은 시간에 소수인지 아닌지 판단할 수 있는 방법을 모색했다. 이에 따라 1877년에는 페르마 소수들을 위한 Pépin's test 가, 1878년엔 Proth 의 정리, 1856년엔 메르센느 소수들을 위한 Lucas–Lehmer test 등이 발견되었다. 현대에 가장 많이 쓰이는 알고리즘으로는 APRT-CL, ECPP, AKS 등이 있지만 여전히 느리다. 오랜 시간동안 소수는 순수 수학 외에 아무 쓸모가 없다고 판단되었으나, 1970년 발명된 RSA 암호 방식 ( 소인수 분해가 오랜 걸린다는 것을 이용) 을 통해 그 생각이 완전히 바뀌게 되었다.
1 에대한 논란
19세기 까지 많은 수학자들은 1을 소수로 취급했었다. Derrick Norman Lehmer 의 소수리스트에도 1956년 까지 1을 소수로 취급해 소수가 1 부터 나와있었다. 게다가 Stern 과 Zeisel 의 업적처럼 1을 소수로 간주해 쌓은 많은 정리들이 있다. Henri Lebesgue 은 소수를 1로 간주했던 마지막 수학자 였다.
소수에 대한 여러가지 정리
0 = wz + h + j − q
0 = (gk + 2g + k + 1)(h + j) + h − z
0 = 16(k + 1)3(k + 2)(n + 1)2 + 1 − f2
0 = 2n + p + q + z − e
0 = e3(e + 2)(a + 1)2 + 1 − o2
0 = (a2 − 1)y2 + 1 − x2
0 = 16r2y4(a2 − 1) + 1 − u2
0 = n + l + v − y
0 = (a2 − 1)l2 + 1 − m2
0 = ai + k + 1 − l − i
0 = ((a + u2(u2 − a))2 − 1)(n + 4dy)2 + 1 − (x + cu)2
0 = p + l(a − n − 1) + b(2an + 2a − n2 − 2n − 2) − m
0 = q + y(a − p − 1) + s(2ap + 2a − p2 − 2p − 2) − x
0 = z + pl(a − p) + t(2ap − p2 − 1) − pm.
참고로 이 방정식은 다음과 같이 간단히(?) 나타낼 수 도 있다.
(k + 2)((wz + h + j − q)2 − ((gk + 2g + k + 1)(h + j) + h − z)2 − (16(k + 1)3(k + 2)(n + 1)2 + 1 − f2)2 − (2n + p + q + z − e)2 − (e3(e + 2)(a + 1)2 + 1 − o2)2 − ((a2 − 1)y2 + 1 − x2)2 − (16r2y4(a2 − 1) + 1 − u2)2 − (n + l + v − y)2 − ((a2 − 1)l2 + 1 − m2)2 − (ai + k + 1 − l − i)2 − (((a + u2(u2 − a))2 − 1)(n + 4dy)2 + 1 − (x + cu)2)2 − (p + l(a − n − 1) + b(2an + 2a − n2 − 2n − 2) − m)2 − (q + y(a − p − 1) + s(2ap + 2a − p2 − 2p − 2) − x)2 − (z + pl(a − p) + t(2ap − p2 − 1) − pm.)2)
어떠한 자연수 x 이하의 소수의 개수
비록 소수의 개수가 무한하지만, "10만 이하의 소수의 개수는 몇 개 일까?", 나 "무작위로 20자리수를 선택하였을때, 그 수가 소수가 될 확률은 몇 일까?" 등의 질문에 대해 답변하기에는 힘들다. 힘들다는 뜻은 비록 구할 수 있지만 시간이 오래걸린다는 것이다. 어떠한 자연수 x 이하의 소수의 개수를 나타내는 함수는 보통 π(x) 라고 한다. 현대의 몇몇의 알고리즘은 π(x) 의 값을 구하는 것을 빠르게 할 수 있지만 그래도 아직 느리다. 현대의 컴퓨터로는 π(1020) 정도 까지는 빠르게 구할 수 있다. 하지만 그 이상으로 늘어난다면 점점 구하는 시간이 느려지기 때문에 소수의 개수를 대략적으로 나타낼 수 있는 방법을 찾아야 하는데 바로 소수정리인 π(x) 는 대략 x/ln(x) 라는 것이다.
만약에 정확하게 소수의 개수를 구하고 싶다면 위의 공식이 쓸모 없어진다. 따라서 소수를 판별할 수 있는 빠른 방법들을 구상해야 하는데, 가장 유명한 것은 에라토스테네스의 체(현대에 와선 거의 쓰이지 않지만) 이다. 현대에선 AKS 테스트, Lucas-Lehmer 테스트, Solovay-Strassen 테스트 등이 있다.
큰 소수들
2007년 8월 현재 발견된 소수 중 가장 큰 소수로는 232,582,657 − 1 로 9,808,358 자리나 된다. 이는 44번째 메르센느 소수로 2006년 9월 4일에 GIMPS ( 리눅스의 GIMP 가 아니다. Great Internet Mersenne Prime Search 의 약자이다. ) 의 회원인 University of Central Missouri 대학 교수인 Curtis Cooper Steven Boone 이 발견하였다. 하필이면 메르센느 소수들만 찾는다면, 메르센느 소수들의 소수성을 판별할 때, Lucas–Lehmer 테스트가 비교적 메르센느 소수에 빠르게 적용되기 때문이다. 메르센느소수가 아닌 가장 큰 소수는 19,249 × 213,018,586 + 1 로 3,918,990 자리 이다. 현재 전자 프론티어 재단(Electronic Frontier Foundation , EFF) 에선 최초의 1000만자리 소수를 찾는 사람에게 십만달러를, 1억자리 소수에겐 15만 달러를, 10억 자리 소수에겐 50만 달러의 상금을 걸었다. 현재까진 2000년에 1만자리 소수로 5만달러를 타갔다.
풀리지 않은 소수에 관련한 문제들
소수에 관련한 문제들은 무수히 많다. 먼저 그 유명한 리만 가설(Riemann hypothesis , 소수들의 일반적인 분포를 알 수 있다. 물리적인 관점에서 볼 때 소수들의 분포는 무작위적으로 나타낸다고 하지만 수학적인 관점에서 보자면 소수들의 분포는 x 보다 작은 자연수들 중 1/ log x 거나 (소수정리) 작은 구간에서는 대략 루트 x 값과 근사한다.) 이 있으며 이는 증명되지는 않았지만 많은 수학자들은 이 것이 맞다고 생각한다. 리만 가설은 힐베르트가 언급한 23개의 난제들 중 최고봉에 위치한 난제 중에 하나이다. 프랑스 수학자 Louis de Branges 가 풀었다고 주장하지만 틀린것으로 판명이 났다. 대개 유명한 추측들( 예를들어 골드바흐의 추측) 은 비록 증명되지는 않았지만 맞을 확률이 매우 높다.
리만 가설외에도 다음과 같은 추측들이 있다.
수학에서 소수란, 1보다 큰 자연수 들 중에서 1과 자기 자신으로만 나누어 떨어지는 수를 가리키는 말이다. 무수히 많은 소수들이 있다는 것은 기원전 300년 경 위대한 그리스 수학자 유클리드에 의해 증명되었다. 처음 몇 개의 소수들을 나열해 보자면
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,... 로 무수히 많이 있다.
소수에 대한 연구는 정수론에 많은 부분을 차지 하고 있다. 소수에 대해 많은 수학자들이 연구를 하였고, 아직도 몇 가지 기본적인 질문들을 해결하지 못한 것 들이 있다. 예를들어 리만 가설(Riemann hypothesis) 이라던지, 골드바흐 추론(Goldbach conjecture)등은 아직도 몇 세기 동안 해결되지 못한 것들이다. 소수의 빈도수 또한 정수론 학자들에게는 매우 인기있는 주제이기도 하다.
소수의 역사
유클리드 (Euclid)
이집트인들의 기록을 살펴보자면 그들이 소수에 대한 약간에 지식은 있었던 것으로 보인다. 예를들어 Rhind papyrus 에선, 여러가지 소수들과 합성수 들이 써져 있었다. 그러나 실질적으로 소수에 대한 연구가 시작된 것은 고대 그리스 부터였다. 유클리드 원론(기원전 300년)에선 몇 가지 기본적이고 중요한 증명들이 있는데 예를들면 소수의 무한성도 그 중 하나였다. 또한 유클리드는 메르센느 소수로 부터 어떻게 완전수를 만들 수 있는지도 보였다.
에라토스테네스 체의 원리
에라토스테네스(Eratosthenes)가 만든 에라토스테네스 체( Sieve of Eratosthenes )는 소수를 찾기에는 가장 간단한 방법이지만 현재 큰 소수를 찾는 컴퓨터는 이 알고리즘은 택하지 않았다. 그리스 이후 17세기까지 소수에 대한 연구는 큰 진보를 하지 않았으나 다음과 같은 사실이 발견되었다.
페르마(Pierre de Feramt)
1640년 피에르 데 페르마 (Pierre de Fermat) 는 그의 페르마 소정리 (Fermat's little theorem) 를 발견하고 후에 라이프니치(Leibnitz)와 오일러(Euler)에 의해 증명되었다. 참고적으로 페르마 소정리의 특정 부분은 훨씬 전부터 중국에서도 알려져 있었다. 페르마는 n=4 일때 까지 해 본후 모든 22n + 1 꼴의 수는 소수일 것이라고 추측하였으나 (이들을 페르마 수 라 부른다)그 다음 페르마 수인 232+1 은, 오일러의 노력에 의해 641의 배수임을 보였다. 또한 오일러는 그 다음부터 모든 페르마 수들은 소수가 아님을 발견하였다.
마린 메르센느(Marin Mersenne)
프랑스의 수도사 마린 메르센느(Marin Mersenne) 은 2p - 1 꼴의 소수 ( p 는 소수 ) 를 살펴보았고 이는 나중에 영광스럽게도 메르센느 소수라는 이름이 붙었다.
오일러(Leonhard Euler)
르장드르(Adrien-Marie Legendre)
그 후 19세기 초에, 르장드르( Legendre )와 가우스(Gauss) 는 독립적으로 x가 무한대로 증가할 때, 자연수 x 까지의 소수의 개수는 x/log(x) 에 접근함을 보였다. 1859년에 리만은 그의 논문서 제타 함수(zeta-function) 에 대한 아이디어를 남겼다. 그것을 통해서 소수정리를 증명 할 수 있었고, Hadamard 와 de la Vallée Poussin 에 의해 독립적으로 위 리만의 아이디어를 이용해 1896년 소수 정리를 증명하였다.
수학자들은 어떤 큰 수에 대해서 나누기 너무 오랜 시간이 걸리기 위해 짧은 시간에 소수인지 아닌지 판단할 수 있는 방법을 모색했다. 이에 따라 1877년에는 페르마 소수들을 위한 Pépin's test 가, 1878년엔 Proth 의 정리, 1856년엔 메르센느 소수들을 위한 Lucas–Lehmer test 등이 발견되었다. 현대에 가장 많이 쓰이는 알고리즘으로는 APRT-CL, ECPP, AKS 등이 있지만 여전히 느리다. 오랜 시간동안 소수는 순수 수학 외에 아무 쓸모가 없다고 판단되었으나, 1970년 발명된 RSA 암호 방식 ( 소인수 분해가 오랜 걸린다는 것을 이용) 을 통해 그 생각이 완전히 바뀌게 되었다.
1 에대한 논란
19세기 까지 많은 수학자들은 1을 소수로 취급했었다. Derrick Norman Lehmer 의 소수리스트에도 1956년 까지 1을 소수로 취급해 소수가 1 부터 나와있었다. 게다가 Stern 과 Zeisel 의 업적처럼 1을 소수로 간주해 쌓은 많은 정리들이 있다. Henri Lebesgue 은 소수를 1로 간주했던 마지막 수학자 였다.
소수에 대한 여러가지 정리
- 10 이상의 모든 소수들은 일의 자리수가 1,3,7,9 중 하나이다.
- 만약 소수 p 가 두 정수 ab 의 곱을 나눌때, p | a 거나, p | b 이다. 이는 유클리드의 보조정리서 나와있으며 소인수분해가 유일하다는 데에 쓰인다.
- p 가 소수이고 a 가 임의의 정수일때, p | ap − a 이다. ( 페르마 소정리)
- p 가 소수일때, p | (p-1)! + 1 이다. ( 윌슨 정리 )
- n 이 1 보다 큰 정수일때, n < p < 2n 을 만족하는 소수 p 가 적어도 한 개 이상 존재한다. (베르뜨랑 공준, 쳬비셰프 정리)
- 등차수열 a, a + q, a + 2q, a + 3q,… 에서 만약 a 와 q 가 서로소 이면 이 무한 등비수열에는 무수히 많은 소수가 존재한다. ( 등차수열에 대한 디리클레 정리 )
- 소수개수 정리에 따르면 x 가 증가함에 따라 x 이하의 소수의 수는 1/ln x 에 접근한다. 참고로 이는 이렇게 나타낼 수 있다.
이 때, π(x) 는 x 이하의 소수의 개수를 나타낸다.
소수의 개수
소수가 무한히 많다는 사실에 대한 증명은 그리스 수학자 유클리드에 의해 그의 저서 원론 제 9권의 20번째 명제에 증명이 되어있다.
유한개의 아무 소수들의 집합을 고려하자. 그 소수들을 모두 곱한 후, 1을 더하면 그 결과는 우리가 고려했던 유한개의 소수들로 나누어 떨어지지 않는다. 왜냐면 그 소수들로 나눌 경우 나머지가 1이 남기 때문이다. 모든 합성수들은 소수들의 곱으로 표현가능하기 때문에, 이 수는 소수이며 아니면 이 수를 나누는 우리가 처음에 고려했던 집합에 포함되지 않는 소수 또는 소수들이 존재한다. 따라서 우리가 처음에 고려했던 집합에 포함되지 않는 소수가 적어도 하나 더 생기게 된다. 이말은 우리가 처음에 유한집합을 어떠한 크기로 잡아도 언제나 그 집합에 포함되지 않는 소수가 생기기 때문에, 무한히 많은 소수가 존재한다.
때로는 이 유클리드의 증명 서, 1을 더할 때, 그 수는 언제나 소수이다 로 끝낼 때가 있는데 이는 다음과 같은 반례를 통해 쉽게 아니라는 것을 볼 수 있다. 만약 유한개의 집합을 2 , 3, 5 ,7, 11, 13 로 잡게되면 (2 · 3 · 5 · 7 · 11 · 13) + 1 = 30,031 = 59 · 509 ( 59,509 모두 소수 ) 임을 볼 수 있다. 따라서 위 증명 중, 줄친 부분이 빠지만 틀린 증명이 된다. 이 말고도 소수의 무한함에 대한 다른 많은 증명이 있는데, 예를들어서 오일러는 소수들의 역의 합이 발산함을 보임으로써, 소수들이 무한함을 보였다. 골드바흐는 페르마 소수를 통해 소수의 무한함을 보였다. 그 외에도 쿰머(Kummer) 등이 가지 각색의 방법으로 증명하였다.
소수를 찾는 공식 ?
현재까지 알려진 소수를 효과적으로 찾는 공식은 존재하지 않는다. 예를들어서 f(n) = n2 − n + 41 라는 함수는 n 이 0 부터 40,43 까지 결과값이 모두 소수이지만 41이나 42일 때 합성수이다. 참고로 아래의 26원 디오판타스 방정식은 소수를 찾는데 사용될 수 있다. 1976년에 Jones et al. 이 주어진 수 k+2 가 아래 14개의 방정식을 모두 만족한다면 그 수는 소수임을 증명하였다. 그 방정식은 다음과 같다.
참고로 이 방정식은 다음과 같이 간단히(?) 나타낼 수 도 있다.
(k + 2)((wz + h + j − q)2 − ((gk + 2g + k + 1)(h + j) + h − z)2 − (16(k + 1)3(k + 2)(n + 1)2 + 1 − f2)2 − (2n + p + q + z − e)2 − (e3(e + 2)(a + 1)2 + 1 − o2)2 − ((a2 − 1)y2 + 1 − x2)2 − (16r2y4(a2 − 1) + 1 − u2)2 − (n + l + v − y)2 − ((a2 − 1)l2 + 1 − m2)2 − (ai + k + 1 − l − i)2 − (((a + u2(u2 − a))2 − 1)(n + 4dy)2 + 1 − (x + cu)2)2 − (p + l(a − n − 1) + b(2an + 2a − n2 − 2n − 2) − m)2 − (q + y(a − p − 1) + s(2ap + 2a − p2 − 2p − 2) − x)2 − (z + pl(a − p) + t(2ap − p2 − 1) − pm.)2)
어떠한 자연수 x 이하의 소수의 개수
비록 소수의 개수가 무한하지만, "10만 이하의 소수의 개수는 몇 개 일까?", 나 "무작위로 20자리수를 선택하였을때, 그 수가 소수가 될 확률은 몇 일까?" 등의 질문에 대해 답변하기에는 힘들다. 힘들다는 뜻은 비록 구할 수 있지만 시간이 오래걸린다는 것이다. 어떠한 자연수 x 이하의 소수의 개수를 나타내는 함수는 보통 π(x) 라고 한다. 현대의 몇몇의 알고리즘은 π(x) 의 값을 구하는 것을 빠르게 할 수 있지만 그래도 아직 느리다. 현대의 컴퓨터로는 π(1020) 정도 까지는 빠르게 구할 수 있다. 하지만 그 이상으로 늘어난다면 점점 구하는 시간이 느려지기 때문에 소수의 개수를 대략적으로 나타낼 수 있는 방법을 찾아야 하는데 바로 소수정리인 π(x) 는 대략 x/ln(x) 라는 것이다.
π(x)와 x/ln(x) 의 값 비교
만약에 정확하게 소수의 개수를 구하고 싶다면 위의 공식이 쓸모 없어진다. 따라서 소수를 판별할 수 있는 빠른 방법들을 구상해야 하는데, 가장 유명한 것은 에라토스테네스의 체(현대에 와선 거의 쓰이지 않지만) 이다. 현대에선 AKS 테스트, Lucas-Lehmer 테스트, Solovay-Strassen 테스트 등이 있다.
큰 소수들
2007년 8월 현재 발견된 소수 중 가장 큰 소수로는 232,582,657 − 1 로 9,808,358 자리나 된다. 이는 44번째 메르센느 소수로 2006년 9월 4일에 GIMPS ( 리눅스의 GIMP 가 아니다. Great Internet Mersenne Prime Search 의 약자이다. ) 의 회원인 University of Central Missouri 대학 교수인 Curtis Cooper Steven Boone 이 발견하였다. 하필이면 메르센느 소수들만 찾는다면, 메르센느 소수들의 소수성을 판별할 때, Lucas–Lehmer 테스트가 비교적 메르센느 소수에 빠르게 적용되기 때문이다. 메르센느소수가 아닌 가장 큰 소수는 19,249 × 213,018,586 + 1 로 3,918,990 자리 이다. 현재 전자 프론티어 재단(Electronic Frontier Foundation , EFF) 에선 최초의 1000만자리 소수를 찾는 사람에게 십만달러를, 1억자리 소수에겐 15만 달러를, 10억 자리 소수에겐 50만 달러의 상금을 걸었다. 현재까진 2000년에 1만자리 소수로 5만달러를 타갔다.
풀리지 않은 소수에 관련한 문제들
소수에 관련한 문제들은 무수히 많다. 먼저 그 유명한 리만 가설(Riemann hypothesis , 소수들의 일반적인 분포를 알 수 있다. 물리적인 관점에서 볼 때 소수들의 분포는 무작위적으로 나타낸다고 하지만 수학적인 관점에서 보자면 소수들의 분포는 x 보다 작은 자연수들 중 1/ log x 거나 (소수정리) 작은 구간에서는 대략 루트 x 값과 근사한다.) 이 있으며 이는 증명되지는 않았지만 많은 수학자들은 이 것이 맞다고 생각한다. 리만 가설은 힐베르트가 언급한 23개의 난제들 중 최고봉에 위치한 난제 중에 하나이다. 프랑스 수학자 Louis de Branges 가 풀었다고 주장하지만 틀린것으로 판명이 났다. 대개 유명한 추측들( 예를들어 골드바흐의 추측) 은 비록 증명되지는 않았지만 맞을 확률이 매우 높다.
리만 가설외에도 다음과 같은 추측들이 있다.
- 유클리드 소수의 무한함. 유클리드 소수가 무엇인지는 여기로 가서 참고하실것
- 강한 골드바흐 추측 (Strong Goldbach conjecture). 2보다 큰 모든 짝수는 2개 소수의 합으로 표현할 수 있다.
- 약한 골드바흐 추측(Weak Goldbach conjecture). 5보다 큰 모든 홀수는 3개의 소수의 합으로 표현할 수 있다.
- 쌍둥이 소수의 무한성. 유클리드는 무한히 많은 쌍둥이 소수가 존재한다고 했다. 하지만 아무도 증명하지 못했다.
- Polignac 의 추측(Polignac's conjecture). 모든 정수 n 에 대하여 차이가 2n 이 나는 소수들의 쌍이 무수히 많이 존재한다. n=1 이면 쌍둥이 소수의 무한성에 대한 문제가 된다.
- 메르센느 소수의 무한성. 이것이 증명되면 완전수의 무한성도 같이 증명된다.
- n2 + 1 꼴의 소수의 무한성
- 르장드르의 추측 (Legendre's conjecture): n2 와 (n + 1)2 사이엔 소수가 적어도 한 개 이상 존재.
******
참고자료
http://en.wikipedia.org/wiki/Prime_number
http://en.wikipedia.org/wiki/Prime-counting_function
http://en.wikipedia.org/wiki/AKS_primality_test
http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions
http://en.wikipedia.org/wiki/Prime_number_theorem
http://en.wikipedia.org/wiki/Riemann_hypothesis
'Mathematics' 카테고리의 다른 글
| 암호학(Cryptography) 의 모든 것 (2) | 2008.05.11 |
|---|---|
| 여러가지 재미있는 풀이들 (0) | 2008.04.20 |
| 피타고라스 수 (Pythagorean triple) 와 그 해 (2) | 2008.02.20 |
| 세계 각국의 수학 올림피아드 문제를 모아놓은 사이트 (1) | 2008.02.13 |
| 여러가지 소수 (Prime number)들 (5) | 2007.12.28 |
