2이상의 모든 자연수는 소수의 곱으로 유일하게 나타낼 수 있다.

By | 2008/07/30

유명한 정리(?)입니다.

모든 자연수는 소수의 곱으로 유일하게 나타낼 수 있다.

그런데 그것을 어떻게 증명할지에 대해서는 생각하지 못했네요.

그러다 이번에 그 증명을 보게 되었고, 이를 기록하기로 하였습니다.

 

6.042J / 18.062J Mathematics for Computer Science – Week6

 

이를 영어로 적은 자료만 남기면 후에 검색하기 힘드니

간단하게나마 제가 이해한 것을 적겠습니다.

 

 

먼저, 모든 자연수는 소수의 곱으로 나타낼 수 있음을 증명하겠습니다.

여기에 쓰인 증명법은 Strong Induction입니다.

Strong Induction은 다음과 같은 방법입니다.

 

6.042J / 18.062J Mathematics for Computer Science – Week3

기존의 Induction에서 가정할 때 P(n)만이 참(true)임을 가정하는 것이 아니라

P(0)부터 P(n)까지 모두 참(true)임을 가정한 후 P(n+1)이 참임을 증명합니다.

 

먼저 n = 1일 때는 소수 집합의 공집합 곱으로 표현이 가능합니다.

다음으로 n보다 작은 모든 자연수 k은 소수의 곱으로 나타낼 수 있다고 가정한다면

n이 소수의 곱으로 나타낼 수 있음을 얘기하겠습니다.

만약 n이 소수라면 참입니다.

만약 n이 소수가 아니라면 n은 n보다 작은 a, b의 곱으로 표현이 가능합니다.

여기서 a와 b는 n보다 작기에 가정에 의하여 소수의 곱으로 나타낼 수 있습니다.

따라서 n은 소수의 곱으로 나타낼 수 있습니다.

 

 

다음으로 이렇게 나타낸 소수의 곱이 유일함을 증명하겠습니다.

여기서 쓰인 원리는 well-ordering principle입니다.

해당 원리의 뜻은 모든 공집합이 아닌 자연수는 가장 작은 member를 가진다는 겁니다.

그리고 사용한 증명법은 proof by contradiction입니다.

 

가정을 부정하여 소수의 곱으로 나타낼 수 있는 방법이

하나 이상인 자연수의 집합이 존재한다고 하겠습니다.

그럼 well-ordering principle에 따라 가장 작은 자연수가 존재합니다.

이를 n이라고 하겠습니다.

그럼 n은 다음과 같이 표현이 가능합니다.

 

그럼 p₁은 n을 나눌 수 있기에, q₁q₂… q_k도 나눌 수 있습니다.

(한국어로 어떻게 얘기해야할 지 모르겠습니다.

다만, n = p₁* Q + 0라는 말을 나눌 수 있다는 말로 표현하였습니다.

나누어 떨어진다는 표현이 있지만 주어와 목적어를 어떻게 두어야 할지 모르겠습니다.;;;)

Lemma 4.2에 따라 p₁은 q_i를 나눌 수 있습니다.

하지만 q_i는 전부 소수입니다.

따라서 p₁= q_i가 되는 것입니다.

그리하여 처음 식에는 p₁를, 두 번째 식에는 q_i를 나누면,

n/p₁는 소수의 곱으로 나타내는 두 가지 방법이 있음을 알 수 있습니다.

하지만 가정에서 가장 작은 자연수를 n이라고 하였기에 이는 모순입니다.

 

따라서 모든 자연수는 소수의 곱으로 유일하게 나타낼 수 있습니다.

 

 

생각외로 적기 어렵네요.^^;;

여하튼 이렇게 증명이 되어 정리가 나왔습니다.

역시 자세한 것은 영어로 된 원문을 읽는 것이 좋을 듯싶습니다.^^ㅜ

 

 

참조

004.pdf

 

 

PS

이 글을 작성하기 위해 자료를 검색하다 재미있는 문서를 하나 찾았습니다.

Dangers of proof by contradiction (advice for amateurs or beginners)

 

왜 이 문서에 흥미를 느꼈냐면

첫째로 이산수학 시간에 배운 증명법 중 proof by contradiction이 헷갈립니다.

조금만 복잡해도 어느 것을 부정하여 어떻게 모순을 이끌어야할지

그것을 찾아내는 것이 상당히 어려웠습니다.

 

둘째로 해당 문서가 있는 위치입니다.

http://research.microsoft.com/~cohn/Thoughts/contradiction.html

research.microsoft.com입니다.

마이크로소프트에서 이런 문서를 제공할리 이유가 없다는 생각에 살펴보니

역시 해당 회사 직원이 쓴 개인 문서입니다.

하지만 글쓴이의 배경은 화려하네요.

MIT 수학과 출신에 하버드에서 박사를 받았군요.(쿨럭…)

그 정도 되어야지 마이크로소프트 연구원으로 들어가는군요…^^;;OTL…

7 thoughts on “2이상의 모든 자연수는 소수의 곱으로 유일하게 나타낼 수 있다.

  1. object

    Microsoft Research (MSR)은 우리가 흔히 아는 Microsoft Corporation과 독립적인 기관입니다. 거의 탑 대학 수준의 연구진과 (수 많은 ACM Fellow에 Field 메달리스트 등) 상당히 최고 수준의 연구 실적을 자랑하죠. 솔직히 말해 돈에 구애 받지 않고 맘껏 연구하는 거의 유일한 사기업이 운영하는 연구소가 아닌가 생각합니다. MSR의 PhD 연구원으로 가려면 그 해 탑 PhD어야 갈까말까할 정도로 들어가기 힘듭니다.

    Reply
    1. NoSyu

      아.. 독립 연구기간이군요.
      그럼 Xenox의 PARC와 비슷한 곳인가요??
      탑 PhD여도 들어갈까말까라…. 역시 대단한 곳이군요.;;;;;

      Reply
  2. 까칠한JC

    Microsoft와 Microsoft Research가 연동하여 이/공계열에서 필요한 소프트웨어를 많이 만들어 내기도 합니다. 또한 관련 문서도 제법 제공하는 편이기 때문에 관련 자료 찾는 곳으로 이용하고 있기도 합니다. ^^ 예로 제가 처음 Microsoft에서 찾은 자료는 Bayesian Network를 생성하는 프로그램이었습니다.

    Reply
    1. NoSyu

      독립되어 있어도 역시 연결은 되어있네요.^^
      (아.. 독립과 연결은 다른 말인가요?^^;;;;)
      Bayesian Network이 무엇인가 보니 처음 보는 것…;;;;
      구글 검색에서 네 번째로 나오네요.^^;;;

      Reply
  3. 환자

    음 모든 자연수는 소수의 곱으로 유일하게 나타낼 수 있다.. 라기보다는 모든 자연수는 유일한 소인수분해 방법을 갖는다라고 하는 게 더 적절할 것 같습니다. 저는 이 증명을 시중에 나와있는 문제집 ‘명품수학 중학교 2학년’ 에서 접했는데, 중학생 대상이라 그런건지 굉장히 설명이 잘 되어 있었습니다. 요즘에도 팔리고 있는지는 모르겠습니다.

    Reply
    1. NoSyu

      아.. 소인수분해… 맞네요.^^
      지적 고맙습니다.
      명품수학 중학교 2학년이라….
      상당히 어려워보이네요.OTL….
      (이상하게 고등학교 수학보다 중학교 수학이 어려웠던 기억이….;;;;;)

      Reply
  4. NoSyu Post author

    기존의 제목에서 ‘모든 자연수’라고 하였으나
    실제로 1은 소수의 곱으로 표현할 수 없기에
    (소수는 2보다 작을 수 없죠.)
    실제로는 ‘2 이상의’라는 제한이 있어야 합니다.
    문득 예전 글들을 찾아보다가 이 글이 눈에 들어와 간단히 제목만 수정하였습니다.

    Reply

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.