Joy Of Math/생각넓히기 / / 2022. 11. 18. 13:19

소수란? (소수의 다양한 특성)

728x90

소수

 

1. 소수

 소수(Prime Number) : 1보다 크고, 1과 자기 자신을 제외한 다른 수로는 나누어지지 않는 수

 1과 소수 이외의 자연수는 모두 소수의 곱셈으로 나타낼 수 있다. 예컨대 302×3×5이다. 게다가 곱하는 차례를 고려하지 않으면 유일한 방법으로 나타낼 수 있다. 1가지 방법 밖에 없다. 그래서 소수를 '수의 원자'라고도 한다.

그리고 소수 이외의 수는 자연수는 '1과 그 자신 이외의 수를 약수로 가지는 자연수''합성수(Composite Number)'라고 한다.

소수의 성질은 대단히 다양해서 소수를 구하는 공식은 아직 발견되지 않았다.

소수는 우리의 개인 정보를 지키는 암호화 기술에도 활용되고 있어 소수가 가지는 매력을 살펴봅시다.

 

2. 소수에서 규칙성은?

 작은 차례로 소수를 찾아 나갈 때, 그것을 나타내는 데 규칙이 있을까? 지금까지 알려진 바에 따르면, 소수의 등장 방식은 매우 불규칙해 종잡을 수가 없다. 수많은 수학자들이 소수의 규칙을 찾아내소수려고 노력했지만, 그 규칙성을 찾아내지 못했다.

 소수는 고대 그리스의 수학자 '유클리드(에우클레이데스)'가 약 2300년 전에 쓴 '원론'에도 적혀 있다. 이처럼 오래전부터 연구되고 있음에도 불구하고, 현재까지도 소수의 완전한 규칙성은 발견되지 않았다. 그러면 소수에는 정말 규칙성이 없는 것일까?

소수원에 보이는 규칙성과 불규칙성(플리히타의 소수원)

소수원(Prime Number Cross) : 출처 https://surpriser.tistory.com/1045

 

위 그림은 '플리히타(Peter Plichta)의 소수원(Prime Number Cross)'이라는 것이다. 숫자를 시계 방향으로 원처럼 나열해 갈 때 1부터 순서대로 나열하면서, 24마다 한 줄 밖의 원으로 이동하도록 배치되어 있다. 소수는 붉은색 원 속의 숫자로 나타냈다.

 얼핏 보고도 알 수 있듯이, 23을 제외하면 소수는 중심에서 바깥을 향해 어떤 특정 방사상의 선 위에 있으며, 다른 직선 위에는 나타나지 않는다. 이것으로 미루어 보면, 소수에 어떤 규칙성이 있는 것처럼 보이기도 한다.

하지만 소수를 나타내는 각각의 직선에 주목하면, 각 직선에서 소수가 나타나는 방식은 불규칙함을 알 수 있다. 거기에는 규칙성이 전혀 없는 것처럼 보인다. 이처럼 '피터 플리히타'의 소수원에서 소수의 불가사의함을 엿볼 수 있다.

 

3. 소수를 골라내는 가장 오래되고 유일한 방법(에라토스테네스의 체)

소수를 확실하게 찾는 유일한 방법은 '에라토스테네스의 체(Eratosthenes' sieve)'이다. 고대 그리스의 수학자 '에라토스테네스(기원전 275~기원전 194)'가 생각해 냈다고 한다.

 이 방법에서는 먼저 2 이상의 수를 적어 나열한다. 무한히 나열하는 것은 불가능하므로, 적당한 수까지 적어두도록 하자. 그다음 맨 앞의 2를 그대로 두고, 그 뒤에 오는 2의 배수를 없앤다. 남은 수 가운데 2 다음에 오는 것은 3이다. 그리고 그 3을 그대로 두고, 3의 배수를 없앤다. 이어 남은 수의 맨 앞의 5이므로... 같은 방법으로 계속해 간다. 그렇게 하면 최종적으로 남은 수는 소수가 된다.

이 방법은 매우 단순하지만 현재로서는 확실하게 소수를 발견하는 이 이상의 방법은 없다. 아래표에서 '에라토스테네스의 체'라는 방법을 이용하여 실제로 100까지의 소수를 구해보자.

  2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

방법) '에라토스테네스의 체'의 방법

1) 먼저 2부터 100까지 적어둔다.

2) 2를 제외하고 2의 배수를 제거한다.

3) 3을 제외하고 3의 배수가 되는 수를 제거한다.

4) 5를 제외하고, 5의 배수가 되는 수를 제거한다.

5) 7을 제외하고, 7의 배수가 되는 수를 제거한다.

6) 11을 제외하고, 11의 배수가 되는 수를 제거한다.

7) 이것을 반복한다. 마지막에 남은 것들이 소수이다.

 

4. 소수의 공식

소수의 공식이 있을까?

플리히타의 소수원에서는 어떤 종류의 규칙성 같은 것도 보였다. 하지만 완전한 규칙성은 드러나지 않았다.

소수의 규칙성을 발견해 모든 소수를 구할 수 있는 공식을 유도하는 것은 수학자들의 꿈이다. 모든 소수는 무리이지만, 일부 소수를 발견할 수 있는 식은 몇 가지 알려져 있다.

 독일의 수학자 '레온하르트 오일러(1707~1783)''어떤 수와 그보다 1큰 수를 곱하고, 거기에 41을 더한 것이 소수가 된다.'는 사실을 발견했다. '어떤 수'n이라고 하고 식으로 나타내면 n×(n+1)+41이 된다.

예컨대 '어떤 수'5라고 하면, 5×(5+1)+41=71이며, 이것은 소수이다. 그러나 '어떤 수'가 무엇이든지 소수가 되는 것은 아니다. 예를 들어 40일 때는 40×(40+1)+41=41×41=1681이 된다. 168141로 나눌 수 있으므로 소수가 아니다. 오일러가 발견한 식으로는, n0~39에서는 연속해서 소수를 만들어 낼 수 있다. 그러나 n40일 때는 소수가 아니다.

 그리고 오일러가 발견한 식 외에도 소수의 일부를 만들어내는 식이 많이 발견되어 있다. 다음은 소수의 일부를 만들어내는 다른 식들을 나열한 것이다. 그러나 이들도 반드시 소수가 되는 것은 아니어서 n의 값에 따라 소수가 되지 않는 경우도 많다.

소수의 일부를 만들어 내는 식

1) n×(n+1)+41 (오일러의 소수의 일부를 만들어 내는 식)

2) 4×n×(n+1)+59

3) n×(n-79)+1601

4) 4n^2+170n+1847

5) n^2+n+17

6) 2n^2+29

7) 2n^2+2n+19

 

5. 소인수 분해

자동차의 번호판의 수나 휴대폰 전화의 번호를 하나의 수라고 생각할 때 그 수는 소수일까? 소수가 아니라면 어떤 소수의 곱셈으로 나타낼 수 있을까?

어떤 수를 소수의 곱으로 나타내는 것을 소인수 분해라고 한다. , '합성수(1과 그 자신 이외의 수를 약수로 가지는 자연수)'를 소수의 곱셈으로 나타내는 것을 '소인수 분해(Prime Factorization)'라고 한다.

이른바 수를 '원자'로 분해하는 것이다. 소인수 분해는 그 수를 나눌 수 있는 소수를 찾아 나가는 작업이다. 먼저 작은 소수로 나누어보고, 나누어떨어지면, 더 큰 소수로 나누어 본다. 이렇게 해서 나누어 떨어지는 소수를 찾아 나간다. 이것을 차례로 계속하다가 마지막으로 소수가 남으면 끝난다.

비교적 작은 수에서는 문제가 없지만, 큰 수가 될수록 소인수 분해는 매우 어려워진다.

왜냐하면 작은 수로는 나누어떨어지지 않는 것이 나오는 경우가 있기 때문이다. , 큰 소수를 찾지 않으면 안 된다. 큰 소수를 찾으려면 기본적으로 '에라토스테네스의 체'를 사용하는 수밖에 없다. 거대한 수가 되면 컴퓨터를 사용해도 엄청난 시간이 걸린다.

소인수 분해

 

소인수 분해를 이용한 RSA암호 활용

인터넷 쇼핑이나 개인정보를 암호화 하는데 유용하게 사용되는 기술 가운데 소인수 분해를 이용한 것이 있다. 바로 ‘RSA암호이다.

 'RSA 암호'는 거대한 2개의 소수를 곱한 수를 '열쇠'로 해서 중요한 정보를 암호화하는 것이다. 열쇠가 어떤 소수를 곱한 것인지 알지 못하면, 암호화된 정보를 해독할 수 없다. 거대한 수의 '소인수 분해'를 단시간에 하기는 불가능하므로, 바탕이 되는 소수를 아는 사람 이외에는 해독할 수 없는 것이다.

예를 들면 38,724,2994,391×8,819로 소인수분해를 하는 것은 매우 어렵다. 이보다 훨씬 큰 수를 소인수분해하기가 더 어려울 것이다.

 RSA 암호는 인터넷 쇼핑 등에서 남에게 알려지지 않고 신용 카드 번호를 송신하는 메커니즘이나, 시청료를 지불한 사람만이 볼 수 있는 텔레비전 방송 등 다양한 곳에서 이용되고 있다. 현대 사회는 거대한 소수가 유지하고 있다고 해도 좋을 것이다.

 

6. 소수의 판단

1) 메르센 소수

 '메르센 수(Mersenne number)'2^n -1 형태의 수를 말하며, M(n)으로 표기한다. 예컨대 M(10)=2^10 -1=1023이다. '메르센 소수(Mersenne prime)'는 메르센 수 중 '소수(Prime Number)'인 것을 말한다. 따라서 M(n)이 소수면 n도 소수이다. 하지만 역으로 n이 소수라고 해서 항상 M(n)도 소수가 되는 것은 아니다. 아주 큰 '메르센 소수'는 컴퓨터를 통해 발견되었다. 지금까지 발견된 '메르센 소수'를 정리하면 다음과 같다. (사이에 아직 메르센 소수가 존재할 가능성이 남아있는 것은 번호에 *표시를 붙였음)

번호 n 자리수 발견일 발견자
1 2 1 기원전 430년 경 고대 그리스 수학자
2 3 1 기원전 430년 경 고대 그리스 수학자
3 5 2 기원전 300년 경 고대 그리스 수학자
4 7 3 기원전 300년 경 고대 그리스 수학자
5 13 4 1456 Unknown
6 17 6 1588 피에트로 카탈디
7 19 6 1588 피에트로 카탈디
8 31 10 1772 레온하르트 오일러
9 61 19 1883 이반 미흐비치 페르부쉰
10 89 27 1911 R. E. Powers
11 107 33 1914 R. E. Powers
12 127 39 1876 에두아르 뤼카
13 521 157 1952 130 라파헬 로빈슨
14 607 183 1952130 라파헬 로빈슨
15 1,279 386 1952 625 라파헬 로빈슨
16 2,203 664 1952 107 라파헬 로빈슨
17 2,281 687 1952 109 라파헬 로빈슨
18 3,217 969 1957 98 한스 리젤
19 4,253 1,281 1961 113 알렉산더 허비츠
20 4,423 1,332 1961113 알렉산더 허비츠
21 9,689 2,917 1963 511 도널드 길리스
22 9,941 2,993 1963 516 도널드 길리스
23 11,213 3,376 1963 62 도널드 길리스
24 19,937 6,002 1971 34 브리언트 터커맨
25 21,701 6,533 1978 1030 랜돈 커트 놀 로라 니켈
26 23,209 6,987 1979 29 랜돈 커트 놀
27 44,497 13,395 1979 48 해리 넬슨 데이빗 슬로빈스키
28 86,243 25,962 1982 925 데이빗 슬로빈스키
29 110,503 33,265 1988 128 월크 콜킷 루크 웰시
30 132,049 39,751 1983 919 데이빗 슬로빈스키
31 216,091 65,050 1985 91 데이빗 슬로빈스키
32 756,839 227,832 1992 219 데이빗 슬로빈스키와 폴 게이지
33 859,433 258,716 1994 14 데이빗 슬로빈스키와 폴 게이지
34 1,257,787 378,632 1996 93 데이빗 슬로빈스키와 폴 게이지 
35 1,398,269 420,921 1996 1113 GIMPS / 조엘 아르멩고
36 2,976,221 895,932 1997 824 GIMPS / 고든 스펜스
37 3,021,377 909,526 1998 127 GIMPS / 롤랜드 클락슨 
38 6,972,593 2,098,960 1999 611 GIMPS / 난야 하이라트왈라 
39 13,466,917 4,053,946 2001 1114 GIMPS / 마이클 카메론
40 20,996,011 6,320,430 2003 1117 GIMPS / 마이클 셰이퍼 
41 24,036,583 7,235,733 2004 515 GIMPS / 조지 핀들리 
42 25,964,951 7,816,230 2005 218 GIMPS / 마르틴 노바크 
43* 30,402,457 9,152,052 2005 915 GIMPS / 커티스 쿠퍼 스티븐 분 
44* 32,582,657 9,808,358 2006 94 GIMPS / 커티스 쿠퍼와 스티븐 분 
45* 37,156,667 11,185,272 2008 96 GIMPS / Hans-Michael Elvenich 
46* 42,643,801 12,837,064 2009 412 GIMPS / Odd Magnar Strindmo
47* 43,112,609 12,978,189 2008 823 GIMPS / Edson Smith 
48* 57,885,161 17,425,170 2013 125 GIMPS / Curtis Cooper 
49* 74,207,281 22,338,618 2015 917 GIMPS / Curtis Cooper 
50 77,232,917 23,249,425 2017 1226 GIMPS / Jon Pace
51 82,589,933 24,862,048 2018 127 GIMPS / Patrick Laroche

출처 : 위키백과

 

2) 무한개의 소수

소수의 개수는 무한할까?

그 답은 2300년 전 '유클리드(기원전 330~기원전 275)''원론'에 이미 적혀있다. 발견된 소수의 뒤에는 반드시 더 큰 소수가 나타난다. , 소수는 무한히 존재한다. 유클리드의 원론에서 다음과 같이 소수가 무한히 존재한다는 것을 증명하였다.

 

소수가 무한히 존재함의 증명

다른 소수 q_1, q_2, q_3, ······, q_n을 써서 다음과 같은 수 N을 만들 수 있다.

N=q_1×q_2×q_3······q_n+1

이 수 Nq_1,q_2,q_3, ······, q_n의 어느 소수로도 나누어떨어지지 않는다. 왜냐하면 어느 소수로 나누더라도 q_1×q_2×q_3······×q_n의 부분은 나누어떨어지지만 1이 남기 때문이다. (가장 작은 소수는 2)

따라서 Nq_1, q_2, q_3, ······, q_n과 다른 소수이든가, 또는 q_1, q_2, q_3, ······, q_n이 아닌 다른 소수로 나누어떨어져야 한다.

따라서 q_1,q_2,q_3, ······, q_n 이외에 새로운 소수 q_n+1이 있다.

이것을 되풀이하면, 차례로 새로운 소수 q_n+2, q_n+3, q_n+4 ······가 발견될 것이다.

, 소수는 무한히 있음을 알 수 있다.

 

출현하는 소수의 빈도는 점차 줄어든다.

 소수는 무한히 존재하겠지만, 언제 나타날지는 예측할 수 없다. 소수는 파악할 수 없는 것처럼 보이지만, 그 성질을 아는 방법이 전혀 없는 것은 아니다. 커다란 수까지 소수를 계속 찾아나가다 보면, 어떤 것을 알아차리게 본다. 수를 100씩 구획해 각 구간에 몇 개의 소수가 있는지 세어 본다. 그러면 큰 수가 됨에 따라 소수가 등장하는 빈도가 적어진다는 사실을 알 수 있다.

그럼 소수는 어느 정도의 비율로 줄어 드는 것일까? 반대로 말하면, 소수는 어떤 빈도로 나타날까? 그 상세한 성질을 알면 소수를 발견하는 공식에 가까워질 것이다. 이 문제에 가장 먼저 파고든 사람은 대천재로 알려진 독일의 수학자이자 물리학자인 '카를 프리드리히 가우스(Carl Friedrich Gauss, 1777~1855)'이다.

 가우스는 15세 때 수를 1000씩 구획하고, 그 안에 나타나는 소수의 개수를 끈질기게 세었다. 어떤 사람에게 쓴 편지에서 가우스는 매일 한가한 시간의 15분 동안 소수의 수를 조사하고, 100만까지 이르지 않았을 때 그만두었다고 적었다그래도 수십만이나 되는 수를 조사한 가우스는 마침내, 처음부터 순서대로 세지 않더라도 어느 수까지 나타나는 소수의 개수를 대강 알 수 있는 식을 발견했다. 소수 정리(Prime Number Theorem)'라고 불린다이 식은 아주 정확한 수를 분명히 말할 수는 없다큰 수가 될수록 정확성은 증가하지만, 완전히 올바른 개수를 나타낼 수는 없다그렇지만 소수가 완전히 불규칙하게 나타나는데도 그 대략의 개수를 간단한 식으로 나타낼 수 있다는 사실이 알려졌다. 여기에서 소수의 신비로움이 엿보인다.

 가우스는 이 식이 성립하는 것을 증명하지는 않았으나, 나중에 다른 수학자에 의해서 몇 가지 방법으로 증명되었다. ‘소수 정리라는 가우스가 발견한 것보다 더 정확하게 소수의 개수를 나타낼 수 있는 식도 발견되어 있다

독일의 수학자 '베른하르트 리만(Bernhard Riemann, 1826~1866)'도 이 소수 정리의 증명을 시도했던 사람이다. '리만'1859년에 '주어진 수보다 작은 소수의 개수에 대해'라는 논문을 발표하고, 어떤 가정 아래 소수 정리를 증명했다. 그 가정을 '리만 추측'이라 한다. '리만 추측'이 옳으면 소수 정리를 증명할 수도 있으나, 현재도 그 추축이 옳은지는 해결되지 않은 채 남아 있다.

 

소수의 개수를 구하는 식(소수정리)

N 실제의 개수 식으로 구한 개수
1000 168 134
10000 1229 1022
100000 9592 8271
1000000 78498 69480
10000000 664579 598971
100000000 5761455 5263741

 

7. 쌍둥이 소수

'쌍둥이 소수'35, 57, 1113처럼 어떤 소수와 2의 차로 늘어선 소수 2개의 짝이다

쌍둥이 소수가 나타나는 빈도는 수가 커지면 커질수록 줄어들어 드물어진다. 그런데 아주 큰 수가 되어도 쌍둥이 소수는 가끔 나타난다. 그러면 쌍둥이 소수는 무한히 존재하는 것일까?

현재 알려져 있는 가장 큰 쌍둥이 소수는 20700자리나 되는 큰 것이다. 3756801695685×2^666669±1 이다. 이 거대한 소수는 201112월에 발견된 쌍둥이 소수는 'Prime Grid'라 불리는 분산 컴퓨팅 프로그램으로 발견되었다.

그러나 앞으로 더욱 큰 쌍둥이 소수가 무한으로 발견될지는 알 수 없다. 수는 무한히 계속되기 때문에 쌍둥이 소수도 무한히 있을 수 있지만, 아직 정확하게 증명되지는 않았다.

그 외의 소수에 대하여 다음과 같은 것들이 있다.

어떤 소수와 4자리 떨어진 소수의 쌍은 '사촌 소수(Cousin Prime)'라 불린다. 예를 들어 37, 711, 1317, 등이다.

그리고 어떤 소수와 6자리 떨어진 소수의 쌍은 매력적인 소수(Sexy Prime)’라 불린다. 예를 들어 511, 713, 1117 등을 말한다.

 

소수 쌍 이름 차이
쌍둥이 소수(Twin Prime) 차이가 2인 두 소수의 쌍 35, 57, 1113
사촌 소수(Cousin Prime) 차이가 4인 두 소수의 쌍 37, 711, 1317
매력적인 소수(Sexy Prime) 차이가 6인 두 소수의 쌍 511, 713, 1117

 

8. 수학의 난제

1) 골드바흐의 추측

‘4 이상의 짝수는 모두 2개의 소수의 덧셈으로 나타낼 수 있다.’라는 미해결 추측이 있다. 이것은 독일의 수학자 '크리스티안 골드바흐(Christian Goldbach, 1690~1765)'가 제시한 추측으로, '골드바흐의 추측(Goldbach's Conjecture)'이라 한다.

 골드바흐의 추측을 작은 짝수로 확인해 보자. 아래의 표에서는 2개의 소수를 더해 얻어지는 수를 나타냈다. 가장 위의 가로행과 가장 왼쪽의 세로열에는 소수가 나열되어 있다. 표의 행과 열이 만나는 곳에는 각각의 소수를 더한 수를 적었다.

예컨대 왼쪽의 3과 위쪽의 5가 만나는 곳은 8이다. (8=3+5) 그밖에 4=2+2, 6=3+3, 10=3+7=5+5, 12=5+7, 등 확실히 2개 소수의 덧셈으로 나타낼 수 있음을 알 수 있다.

2개 소수의 덧셈으로 4 이상의 짝수를 나타내고 있는 이 표를 보면, 36까지의 짝수가 모두 등장한다. 그러면 이 표를 넓혀서, 더하는 소수를 무한히 했을 때 표에 등장하지 않는 짝수가 있을까? 현재는 컴퓨터를 이용해 12억의 10억 배까지의 모든 짝수에 대해 추측이 성립한다는 사실이 확인되어 있다. 그러나 그 후의 짝수에 대해서도 정확히 성립하는지는 아직 아무도 증명하지 못했다.

+ 2 3 5 7 11 13 17 19
2 4              
3   6 8 10 14 16 20 22
5     10 12 16 18 22 24
7       14 18 20 24 26
11         22 24 28 30
13           26 30 32
17             34 36
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 

 

2) 리만 추측

소수 연구의 진전에 큰 공헌을 한 수학자의 한 사람은 오일러이다. 오일러는 모든 자연수를 2제곱해 그 역수를 무한히 더해 나가면 몇이 될까?'라는, 당시 해결되지 않았던 문제를 연구했다. 역수란 2라면 2분의 1, 10라면 10분의 1과 같은 그 수를 분모로 하고 1을 분자로 한 수이다. 그리고 오일러는 그 연구 결과 다음과 같은 발견을 했다. , ‘무한의 덧셈 식을 변형하면, 모든 소수를 나타내는 무한의 곱셈이 된다는 것이다.

그리고 오일러는 이 관계식을 더욱 발전시킨 식을 연구했다. 그 식은 '제타 함수'라는 것이다. '제타 함수(Zeta Function)'는 오일러가 연구했던 식의 2제곱 부분을 2 이외의 수나 음수, 허수(제곱하면 음수가 되는 수) 등의 다양한 수를 대입할 수 있는 식이다.

그리고 수학 최대의 어려운 문제라는 리만 추측제타 함수에 여러 가지 값을 대입했을 때 그 계산 결과가 0이 되는 것은 어떤 값일 때일까를 추측하는 것이다. 이 제타함수가 어떤 성질을 가지고 있는가 하는 문제이다.

리만 추측은 약 150년 동안 풀리지 않고 있다. 미국의 클레이 수학 연구소에서는 100만 달러의 현상금까지 걸었다. 수학의 이 궁극적인 미해결 문제는 지금도 많은 수학자를 괴롭히고 있다.

무한의 덧셈으로 나타낼 수 있는 소수(오일러가 발견한 자연수와 소수를 연결하는 식)

제타 함수 (리만 추측은 이 제타 함수의 성질에 관한 추측임)

출처 : newton highlight

반응형

'Joy Of Math > 생각넓히기' 카테고리의 다른 글

원주각의 성질  (0) 2023.09.14
원과 직선 관계  (0) 2023.09.13
RSA암호 원리  (0) 2022.11.11
원에 내접하는 사각형의 성질  (0) 2021.06.18
입체도형의 길이와 부피  (0) 2021.06.18
  • 네이버 블로그 공유
  • 네이버 밴드 공유
  • 페이스북 공유
  • 카카오스토리 공유