어떤 수가 소수인지 그대는 어떻게 확인하는가?
소수... 영어로는 prime number라고 하는 이 개념을 독자들은 들어본 적이 있는가?
아마 중고등학교 수학시간에 한 번쯤은 들어본 기억이 있을 것이다.
소수의 엄밀한 정의는 "1과 자기 자신만을 약수로 가지는 수"이다.
이때 주의할 점은 자기자신이 1이면 안 된다. 잉? 그냥 1은 해당되지 않는다 이 얘기다.
1과 자기 자신만을 약수로 가진다라... 이것에 해당되는 수는 하나가 아니라 여럿이다.
혹시 생각나는 수들이 있는가?
2를 생각해보자. 2는 소수이다. 왜냐면 약수가 1하고 2, 여기서 2는 자기 자신이기 때문이다.
3을 생각해보자. 3은 소수이다. 왜냐면 약수가 1하고 3, 여기서 3은 자기 자신이기 때문이다.
5를 생각해보자. 아니 그만 생각하자. 이쯤 되니 5도 소수인 것이 바로 느껴진다.
이런 소수들은 세상에 무수히 많다.(무수히 많다는 것이 "귀류법"이라는 방법으로 증명이 되었다. 이에 대해서는 다른 글에서 다시 다루겠다.)
소수들: 2, 3, 5, 7, 11, 13, ...
한 자리 수 내지는 두 자리 수와 같은 작은 수의 세계에서는 어떤 수가 소수인지를 알아내는 것이 쉽다. 일례로 37이 소수인가? 라는 물음에 우리는 비교적 쉽게 "예" 라고 대답할 수 있다. 37이 소수인지의 여부는 직접나눔을 통해 판단한다. 37을 머리속에서 2로도 나눠보고, 3으로도 나눠보고, 5로도 나눠보고, 7로도 나눠보고... 이런 식으로 해서 37을 나누어떨어지게 하는 수가 없는지 확인 해본다는 것이다.
그러나 이 방법은 매우 귀찮고 해당 수보다 작은 모든 수로 해당 수를 나눠봐야 하기에 굉장히 번거롭다. 위의 37과 같은 숫자만 하더라도 37보다 작은 모든 수로 37을 나누어본 후에야 37이 소수인지를 확신할 수 있게 된다.
그렇다면 더 좋은 방법이 없을까? 있다. 그것이 바로 오늘 소개할 "소수판정법"이다. 이름은 이렇게 말했지만, 사실 특별히 거창한 것은 아니다. 독자들이 큰 기대를 하지 말고 들어주었으면 한다.
어떤 수 N이 소수인가? 이런 물음이 있다.
이에 대한 답변을 내는 과정은 N보다 작은 모든 수로 N을 나눠보는 것이라 하였다. 그러나 꼭 모든 수일 필요는 없다. 언제나 루트N 이하의 수로만 N을 나눠보면 된다. 이것이 바로 소수판정법이다.
예시를 들어보자. 97이 소수인지 궁금하다. 이 수 97에 루트를 씌운다. 루트97...
루트 97은 루트81보단 크고 루트100보단 작은 숫자일 것이다. 그런데 여기서 루트81은 사실 9이다. 그리고 루트100은 사실 10이다. 아! 루트97은 잘은 모르겠지만 9와 10사이의 어떤 수일 것이다. 가령 9.57 이런 수인 것이다.
그럼 이제 루트97 이하의 수, 그것은 1,2,3,4,5,6,7,8,9가 될 것이다. 그렇다! 97이 소수인지를 알고 싶으면, 1부터 9까지의 숫자로만 97을 나눠보면 된다.(게다가 1은 사실 필요도 없다)
97이 짝수가 아니므로 2,4,6,8과 같은 짝수들로는 당연히 나누어떨어지지 않는다. 그러니까 최종적으로는 3,5,7,9로만 나눠보면 된다.
이 "소수판정법"은 확인하고자 하는 수가 크면 클수록 더 큰 힘을 발휘한다. 그것은 원래 수 N과 루트N의 차이가 N이 커질수록 커지기 때문인데 이건 너무 복잡한 이야기이므로 생략하겠다.
이 소수판정법을 실생활에 적극적으로... 음... 활용할 일은 물론 없을 것이다.
그러나 나름 재미가 있었다면 좋겠다는 말을 끝으로 글을 마무리해본다.
c.f.) 원리가 궁금한 독자들을 위해 간단히 그 원리를 설명해본다.
아래 식을 보자.
N= 루트N X 루트N
당연한 이야기이다. 만약 N이 소수가 아니라면, N에게는 1하고 N(자기자신)이 아닌 다른 약수가 있다는 이야기일 것이다. 즉 N이 아래와 같이 표현된다는 것이다.
N= a X b (a,b는 자연수)
이때 만약 a=b라면, a=b=루트N 이고
만약 a=b가 아니라면, a,b 둘 중 하나는 반드시 루트 N보다 작을 수밖에 없다.
아! 즉 N이 소수가 아니라면, N에게는 반드시 루트N 이하의 약수가 있다는 얘기가 된다.
이는 다시 말해, N에게 루트N 이하의 약수가 없다면, N은 소수가 아니라는 것이다.
이것이 "소수판정법"의 원리이다.