[수학] 소수(Prime number)에 관한 재미있는 사실들

.

일간베스트 원문링크 www.ilbe.com/5130263640

BGM정보 : 브금저장소 - http://bgmstore.net/view/kM4AK

ㅎㅇ 나는 좆문가 지잡대 수학게이다.

방학동안 할거없어 뒹굴거리며 일베나 하던 중 얼마전에 일베 떡밥으로 골드바흐의 추측

(2보다 큰 모든 짝수는 두 개의 소수의 합으로 표시할 수 있다는 것)을 증명했다는 분이 나왔다.

그 글을 보고 소수가 대체 뭔지 궁금해지면서 관련 내용을 읽고 소수를 소개하려고 한다.

이 글의 차례는

소수의 정의 ---------> 소수의 성질 ----------> 소수의 응용 ----------> 소수의 판별 순으로 작성했다.

1)소수의 정의

두산백과에서 소수를 정의하길 [1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수] 라고 한단다.

조금 외우기 쉽게 말하면 소수는 약수가 2개뿐인 수라고 해도 좋다.

소수는 과학에서 원자같은 존재며(쿼크도 있지만)

인수분해로 더 이상 쪼갤 수가 없다.

까도 까도 나오는 양파같은 존재가아니니 나는 소수가 가장 순수한 수라고 생각한다.

소수가 아닌 양의 정수는 합성수다.

이 정의자체는 모두 알고있으니 할말이 없다. 그런데 조금만 생각해보면 소수의 정의에 뭔가 이상한 구석이 있는 것 같다.

대체 왜 1은 소수가 안되냐 . 1도 1과 자기 자신(1)만을 약수도 가지는데 말이지..

실제로 한동안 1을 소수로 간주한 적도 있었다고 한다. 그러나 현대에 오면서 수학자들은 1을 소수에서 제외하기로 결정했다고 한다. 도대체 왜?

수학의 한 부분인 수론에서는 ‘산술의 기본정리’ 라는 것이 있다.

이 정리의 내용은 모든 수는 ‘단 한가지’ 방법으로만 소인수분해할 수 있다는 것이다.

예를 들면, 6을 소인수분해하라고 하면 2x3 이다. 우리가 배운대로라면 이외에 6을 소인수분해할 수 있는 방법은 없다.

만약 1을 ‘소수’라고 한다면 6은 1x2x3, 1x1x2x3, 1x1x1x2x3 이라고도 할 수 있으며

이는 ‘단 한가지’ 방법으로만 소인수분해할 수 있다는 유일성에 위배되는 것이다.

결국은 우리가 원하는 정리를 살리기 위해 소수의 정의를 우리의 입맛에 맞게 뜯어고친 것이다.

위 예는 수학은 대부분 정의를 먼저 정하고, 정의로부터 파생된 정리들을 만들어 간다고 하지만

반대로 정의를 우리입맛에 맞게 수정함으로써 기존의 정리를 훨씬 깔끔하게 만들 수도 있다는 것이다.

2)소수의 성질

소수란 무엇인지 알았으니 다음으로 할 것은 그렇다면 과연 소수란놈은 유한한가? 아니면 한계가 없이 많은가?를 알아보는 것이다.

결론부터 말하면 소수는 무한히 존재한다. ( 대표적으로 유클리드의 정리)

뭐 수 자체도 9999999999999로 끝없이 만들어 낼 수 있는데 소수도 그에 맞게 끝없이 만들 수 있겠지.

수학적으로 증명하는 방법은 간단하다

기본적으로 소수의 개수가 유한하다고 가정하다고 모순을 이끌어 내는 귀류법이 사용된다. 읽기 어려운 게이들은 스킵

소수의 개수가 반대로 유한하다고 가정하자.

집합 P=(N_1, N_2, N_{3, ... ,} N_m) m≠oo 에 유한개의 소수들을 싹다 끌어 모았다고 가정하자.

그 다음 저 소수들을 다 곱하고 거기에 1을 더한 수 L을 생각하자. 즉 L=N₁XN₂XN₃X˙˙˙XN_m+1 이다

모든 소수를 다 곱해서 1을 더한 수 L은 N_m 보다 크므로 L은 집합 P의 원소가 아니며 따라서 합성수다.

L은 합성수이기 때문에 소수 중 하나로 나누어져야 하는데 위 식을 살펴보면 1덕분에 어떠한 소수도 L를 나눌 수 없다.

즉, 집합 P에는 다른 원소 소수 L이 존재한다.

이는 가정에 모순되므로 결국 소수의 개수는 무한하다.

자 이제 소수는 한계가 없이 내가 원하는 만큼 무진장 찾아낼 수 있다는걸 알아냈다 (그러나 쉽지는 않겠지). 무한의 세계로 온 것이다.

무한의 세계는 광활하지만 일정한 규칙이나 법칙이 있을 수도 있다.

마찬가지로 끝없이 이어진 소수들의 세계에서 몇가지 특수한 규칙이 있는 소수들을 알아보자.

1) 메르센(메르센느) 소수

우선 메르센 수는 M_n=2ⁿ-1 (n≥1) 형태의 수, 즉 2의 거듭제곱 중 1이 모자란 수이다(수식이 익숙하면 하노이 탑이 생각날 것이다).

예를 들어 저 식에서 n대신 1을 집어넣은 3 , n대신 3을 집어넣은 7등은 메르센 수이다.

메르센 수 중에서 소수인 수를 메르센 소수라고 한다. 안타깝게도 메르센 소수가 유한한지 무한한지는 밝혀지지 않았다.

소수는 무한한데 메르센 소수는 유한한지 무한한지 모른다니....

이 메르센 수에 대해 굉장히 많은 이야기가 있는데 그 중에서 한가지를 말하면 M_n 이 메르센 소수이면 n자체가 소수라는 것이다.

예컨대 2¹³-1=8191 은 메르센 수이니 저 2 위에 붙어있는 13이란 수도 소수가 될 것이다.

따라서 메르센 수 중 소수를 찾기위한 후보 검증 1단계는 n이 소수가 아닌놈은 전부 탈락시키는 것이다.

하지만 역으로 n이 소수라고 해서 M_n이 메르센 소수는 아니다(역이 성립하면 메르센 소수를 좀 더찾기 쉽겠지만)

여담으로 44번째 메르센 소수는 n=32,582,657 는 일때인데,

이 수를 시각적으로 보여 주기 위해서는 1페이지 당, 10진수 75개 자리수의 숫자를 50줄씩 쓴 2,616페이지가 필요하단다.

2) 페르마 소수

1번과 비슷하다. 페르마 수는 F_n=2^{2^n} +1 형태의 수이고 페르마 소수는 저 수들 중 소수인 수를 말한다.

페르마는 n대신 0, 1, 2, 3, 4를 대입한 수가 소수임을 관찰하고, n의 모든 값에 대해 Fn은 소수라는 생각을 가졌다.

실제로 페르마 생각이 맞으면 소수를 찾는데 훨씬 편리하겠지만 안타깝게도 F₅는 합성수였다.

그 외에도

쌍둥이 소수 : 두 수의 차가 2인 소수들의 쌍 ex : (3,5)

섹시 소수 : 두 수의 차가 6(six)인 소수들의 쌍 등 여러가지 종류들이 있다.

3)소수의 응용

이제 대충 소수가 뭔진 알겠는데 이게 도대체 우리 생활 어디에다 쓰일까?

내 개인적인 생각이지만 모든 것은 필요에 의해 만들어 지고 필요가 없으면 점점 쇠퇴할 것이다.

나같은 일베충도 어딘가에 필요하기 때문에 만들어 졌겠지...

뭐 여튼간 소수는 우리 생활 곳곳에 쓰인다고 말할 수 있겠다.

당장 구글에 검색해봐도 너무 많아서 대표적인 한가지만 소개하자면 은행등 여러곳에서도 쓰이는 RSA 공개키 암호시스템이 있다.

로널드 라이베스트(Ron Rivest), 아디 샤미르(Adi Shamir), 레너드 애들먼(Leonard Adleman)

이름의 앞글자를 따서 RSA라 지었다고 한다

이 시스템을 간단히 말하면 47과 59의 곱이 2773임을 계산하는 것은 쉽지만,

거꾸로 2773을 소인수분해하여 두 소인수 47과 59를 찾는 것은 쉬운 일이 아니라는 것이다.

이 원리를 이용해 아주 큰 두 소수 p,q를 비밀로 하고, 그의 곱 n=pq를 공개하는 방식이다.

p와 q가 130자리일 때 현재의 컴퓨터로 약 한 달이 걸리며 자리수가 커지면 커질수록 계산을 하는데 걸리는 시간은 기하급수로 늘어난다고 한다.

이 암호시스템을 뚫는 방법은 어떤수를 빠르게 소인수분해 하는 방법이지만,

암호를 연구하는 사람들은 양자 컴퓨터등을 통해 이 시스템을 해결하려고 하고있는 중인데...

(그럼 뚫은 숫자 보다 소수를 더 크게 만들면 되지??)

자연자체도 소수의 법칙을 따르는 경우도 있다.

미국의 남부에는 13년을 주기로 성충이 되는 매미와 7년을 주기로 성충이 되는 7년 매미가 있다고 한다.

맴맴충 ㅠ

그런데 이 매미들은 왜 하필 13년, 7년 소수를 주기로 등장할까???

이 매미들의 전략은 바로 종족 보존을 위해서다.

사실 매미의 천적은 너무나 많다. 새, 다람쥐, 고양이, 개 등등...

이들로 부터 생명을 지키기 위해선 매미의 성장 패턴을 다른 천척의 성장과 달리할 필요가 있다.

예를 들어 매미의 주기가 4년이고 천적의 주기가 6년이면 두 종은 12년마다 만나지만

매미의 주기가 13년이고 천적의 주기가 6년이면 두 종은 78년마다 만나 조금 더 안전해진다.

이 매미들은 처음에는 주기가 짧았다가 안전을 위협받으며 점점 주기를 변화시켰다가 결국 13년, 7년에 맞춰졌다고 한다.

이도 안전해지지 못한다면 다른 소수의 주기를 찾아야 할 것 이다.

소인수분해와 관련된 또 다른 예가 있다.

혹시 큐브라는 영화를 본 적이 있냐?

나는 이런 장르를 좋아해서 큐브 3편 다 봤다.

여튼간 큐브의 기본적인 내용은 몇 명의 사람들이 방마다 함정이 가득한 움직이는 큐브안에 갇히는데

그 죽음의 큐브를 탈출하려고 하면서 여러 가지 갈등이 나오는 그런 영화다.

큐브 안 각 방에는 3자리수 3개로 구성된 ID가 있는데, 이 3개의 ID는 각 방 안 트랩의 유무, 위치 좌표, 움직이는 방향을 나타낸다.

예를 들어 방의 번호가 339, 127, 164라고 하면 127은 소수이므로 저 건너편 방에는 트랩이 있다 이런식이다.

방을 탐색하던 중 같이 갇혀있던 한 수학자가 이 사실을 알아내서 사람들은 함정을 이리저리 피할 수 있게 된다.

(근데 상부에서 이걸 눈치채고 번호를 지워버림)

개인적으로 재밌었던 영화니 한번 보는걸 추천한다.

4)소수의 판별

우리는 지금 많고 많은 자연수라는 냉장고 안에서 홀수가 필요하다고 하자.

홀수 찾기는 어렵지 않다. 1, 3, 5, 7, 9, 11 등등등 홀수가 필요할때마다 우리는 쉽게 꺼낼 수 있다.

만약 엄청 큰 1억 5천만번째 홀수를 꺼내고 싶을때도 간단히 꺼낼 수 있다. 2n-1 이라는 규칙을 이용해 2억 9999만 9999..라고 알 수 있을것이다.

소수도 마찬가지로 우리가 필요할때 언제든지 냉장고에서 골라 꺼낼 수 있을까? 어떤 수가 소수인지 아닌지 알아볼 수는 없을까?

어떤 숫자가 소수인지 판별하는 가장 쉬운? 방법은 그 앞 숫자까지 전부 나눠 보는 것이다.

예컨대 26이 소수인지 알아보고 싶다면 26을 2부터 25까지 다 나눠보면 된다. 그리고 이 방법은 당연히 귀찮다.

조금 더 발전된 방법은 √n 이하까지의 소수로 n을 나눠보면 된다. 예를 들어 107이 소수인지 알아내고 싶다면

2부터 10까지의 소수 10≤√107≤11 로 나눠보면 된다. 훨씬 간단하다.

학교에서 배운 고전적인 방법으로 에라토스테네스의 체가 있다.

수학선생이 억지로 x표 쳐라할때 지루했다 이기

조금더 효과적인 테스트 중에는 법을 이용해 Wilson's Theorem이 있다고 한다. p가 소수일 필요충분조건은

이다

찾아보니 컴게이들은 소수판별법을 컴퓨터로 작성하던데..

def is_prime(n):

if n <= 3:

return n >= 2

if n % 2 == 0 or n % 3 == 0:

return False

for i in range(5, int(n ** 0.5) + 1, 6):

if n % i == 0 or n % (i + 2) == 0:

return False

return True

산은 산이고 물은 물이다...

이외에도 밀러라빈 소수판별법, 인수분해 알고리즘 등 소수를 빠르고 효율적으로 찾기위한 다양한 알고리즘이나 판별법등이 있다고 한다.

내 글은 여기까지임. 몇 시간걸려서 쓰고보니 이런게 이번 방학중에 제일 보람찬 일이다 이기

나처럼 빈둥거리지 말고 자기계발 잘하셈

뭐 소수 정리, P-NP 문제 같은건 생략했다 앙망

3줄 요약

1. 소수는 아주 신비한 수다.

2. 우리가 살아가면서 대부분은 다수를 중시하지만

3. 소수가 필요할때도 의외로 많다.

. .