약수, 배수 그리고 소수 Divisor, multiple and prime number

이전 포스트에서 나눗셈에 대해 알아보았다.

사실 곱셈의 역연산으로써

정수에서 유리수로 이끄는 나눗셈이긴 하지만 말이다.

 

자연수 N에 대해,

N=nq+r (0=< r < n)

n,q,r은 자연수

으로 표현할 수 있을 것이다.

이 때 표현을 N을 n으로 나눌 때, 몫은 q이고, 나머지는 r이라고 한다.

N/n = q + r/n

으로도 나타낼 수 있을 것이다.

여기서 r=0 이면, N/n=q로 자연수가 될 것이다.

그러면, N은 n으로 나눠 떨어진다고 표현할 수 있다.

 

N=abcd 로 표현할 수 있다고 하자.

각 문자는 전부 자연수이다.

그러면, N은 a,b,c,d 각 문자에 대해 나눠떨어진다고 할 수 있고,

a,b,c,d 는 N의 약수라고 할 수 있다.

N은 각 문자들의 배수라고 할 수 있다.

 

M=bcdf 라고 표현할 때,

N과 M이 공통으로 가지고 있는 약수가 있는데,

b,c,d 이다.

b,c,d는 N과 M의 공약수가 될 것이다.

 

L=abcdf 가 있을 때,

L=Nf=aM 이 되므로,

L은 N과 M의 공배수가 된다.

 

N의 약수를 알아보자.

우선, 한 문자만 있는 게 약수일 것이다.

a, b, c, d

두 문자를 곱한 것도 약수일 것이다.

두 문자 소거해도 나머지 두 문자가 남아서 자연수이기 때문이다.

ab, ac, ad, bc, bd, cd

세 문자를 곱한 것도 마찬가지이다.

abc, abd, acd, bcd

네 개 문자를 다 곱한 것도 약수이다.

소거하면 1이 남기 때문이다.

abcd

임의의 자연수를 1로 나누면 그 자연수 그대로 나오므로,

1은 모든 자연수의 약수이다.

a,b,c,d가 서로 다른 자연수이고, 전부 1이 아니라고 하면,

N의 약수는 1 포함해서 16개의 약수가 나온다.

 

하지만, 각 문자가 공약수가 더 있는지 모르는 상태이다.

자연수의 약수가 무엇이 있는지 분석하기 위해서는

약수가 1과 자기 자신 밖에 없는 수가 필요하다.

1은 모든 자연수의 공약수니 어쩔수 없이 약수로 가져야되는 수고,

1과 자기 자신 밖에 약수가 없으면,

다른 수와 공약수가 생기지 않기 때문에 유용하다.

이런 수를 소수(prime number)라고 한다.

소수 p(i) ( i는 1부터 n까지의 자연수 ) 이렇게 표현할 때,

임의의 자연수 N은

N=p(1)*...*p(n) (p(1)부터 p(n)까지 곱했다는 의미다.)

이런 식으로 표현할 수 있다.

 

N=p(1)...p(n)에서 같은 소수(prime number)가 여러개 있다고 하면,

 

N=(p(1)^(m(1))*...*(p(k)^(m(k)))

 

p(i)는 소수 m(i)는 0과 자연수를 표현한 것

i는 1부터 k까지의 자연수이고,

p(i)^(m(i)) 는 p(i)를 m(i)번 곱했다는 의미

 

이런 식으로 표현할 수 있을 것이다.

여러번 곱한 것의 대한 내용은 이 포스트를 보라.

 

 

 

자연수의 약수의 갯수는 어떻게 헤아릴까?

예를 들어 N을

N=(a^3)*(b^5)*(c^2) (a,b,c는 소수(prime number))

이렇다고 하자.

그러면, N=aaabbbbbcc 이렇게 표현될 것이다.

N의 약수는 a,b,c 중에 갯수에 맞게 곱하거나 고르지 않는 경우일 것이다.

예를들어, a는 3개까지 고를 수 있고,

b는 5개, c는 2개 까지 고를 수 있다.

각 수에 대해 아무것도 고르지 않을 경우도 포함해서 생각해야할 것이다.

a에 대한 선택지는

아무것도 안고른다.

한 개만 고른다.

두 개만 고른다.

세 개만 고른다.

4개가 되는 것이다. 

갯수에다 1개 씩 더한게 선택지의 수

b는 5+1=6 개, c는 2+1=3개 이렇게 될 것이다.

그래서 N의 약수의 갯수는 (3+1)*(5+1)*(2+1)=4*6*3=72 개가 될 것이다.

 

위의 표현을 다시 가져와서

N=(p(1)^m(1))*...*(p(k)^m(k))의 약수의 갯수는

(m(1)+1)*...*(m(k)+1) 개가 될 것이다.

 

예를들어 60의 약수의 갯수를 파악해보자.

60은 10과 6의 배수이니

60=6*10

6은 2와 3의 배수이고,

10은 2와 5의 배수이다.

60=2*3*2*5

정리하면, 60=(2^2)*3*5 

60은 2가 2개, 3이 1개, 5가 1개 곱해진 수이다.

약수의 갯수는 (2+1)*(1+1)*(1+1)=3*2*2=12, 12개 이다.

 

약수의 개수를 정수 범위까지 넓히면,

자연수에 '-'붙인 음수까지 포함되어

자연수 약수 갯수의 2배가 될 것이다.

예를 들면,

60=6*10=(2*3)*(2*5)=((-2)*(-3))*((-2)*(-5))=((-2)^2)*(-3)*(-5)이고,

60=(-1)*(-60) 이기 때문에

양의 약수에 '-'기호를 붙인 정수도 약수가 되는 것이다.

그래서 60의 자연수 약수는 12개이지만,

정수 약수는 12*2인 24개이다.

 

약수 갯수 셀 때도 그렇지만,

소수(prime number)는 수를 분석하고 응용할 때 매우 중요한 도구이다.

모든 자연수는 소수의 곱으로 만들 수 있기 때문이다.

1은 모든 소수보다 작은 수지만, 

소수를 안뽑는 경우라고 하면

 1도 0승 이런 식으로 표현할 수 있다.