'최소 공배수' 와 '최대 공약수', '유클리드 호제법' 과 '서로소'.

오늘은 제목에 적은 내용들을 설명해보겠습니다.

 

제목의 역순으로 설명하겠습니다.

 

 

 

 서로소.

서로소는 서로 다른 자연수가 각자

1과 자기자신 이외에 약분되는 자연수가 없는 것을 말합니다.

 

예) 2 와 3 은 서로소입니다.(1로만 약분됨)

4 와 6은 서로소가 아닙니다.(1 과 2로 약분됨)

 

 

 

유클리드 호제법.

유클리드 호제법은 서로 다른 자연수 A,B가 있고

이 A와 B는 각자 서로소 X 최대공약수 의 값을 가집니다.

 

A를 B로 나눴을 때, 나머지의 값이 0이 될 때까지,

이전 수식의 B값을 나머지 값으로 나누고,

이 과정을 반복해서 0이 될 때까지 나누면,

마지막으로 나눈 값이

처음 두 수 A와 B의 최대공약수가 되는 법칙입니다.

 

예) 10 과 6 이 있습니다.

10%6 = 4,

6%4=2,

4%2=0 이므로, 10 과 6의 최대공약수는 2 입니다.

(10은 5X2 이고, 6은 3X2 이므로 서로소X최대공약수가 성립합니다.)

 

그렇다면, 법칙은 너무나 간단한데,

이것이 왜 적용되는지에 대한 궁금증이 생깁니다.

이걸 모르면 공식처럼 외워야 할것 같은데,

이런 법칙이 적용되는 이유를 알면 외울 필요가 없기 때문입니다.

 

찾아본 바로는 증명이 아주 간단하진 않지만,

최대한 간단명료하게 적어보겠습니다.

 

일단, 법칙을 증명하려면 함수(변수)로써 증명해야 합니다.

그래야 어떠한 값을 넣더라도 맞다는 게 증명되기 때문입니다.

 

위의 식을 그대로 변수로써 대입해서 계산해보겠습니다.

 

일단 변수 A와 B가 있고,

A= a*G

B= b*G

( a와 b는 서로소, G는 최대공약수 라는게, 이 법칙의 조건이고,

이걸 증명해서 참이면, 저 조건도 참입니다. )

A를 B로 나눴을 때,

A= q*B + r (q = 몫 , r = 나머지)  입니다.

 

그럼 이걸 다시 쓰면,

a*G = q*b*G + r,

a*G - q*b*G = r,

( a - q*b )G = r 이고,  B = b*G 이기 때문에,

 

A를 B로 나눈 나머지 r과, B는 서로 G라는 공통된 약수를 갖고 있는게 증명됩니다.

따라서, 이 과정을 반복하면 결국 G만 남기 때문에 이 법칙은 증명됩니다.

 

 

 

최대 공약수.

최대 공약수는 서로 다른 자연수 A 와 B를

공통된 수로 나누었을때,

나머지가 0이 되는 수 중에 가장 큰 수입니다.

 

예)

2와 3의 최대공약수는 1.

4와 6의 최대공약수는 2.

6과 9 의 최대공약수는 3.

8과 12의 최대공약수는 4.

 

이건 '정의' 이기 때문에 증명은 아마도(?) 필요 없고,

최대 공약수를 구하는 법은 유클리드 호제법을 쓰면 됩니다.

 

 

 

최소 공배수.

최소 공배수는 서로 다른 자연수 A 와 B가

가지는 공통된 배수 중에, 가장 작은 수를 말합니다.

 

이건 최대공약수가 있으므로 구하는 법이 아주 간단합니다.

 

1. 모든 자연수는 1 이상의 약수를 가집니다.

 

2. 그렇다면 A와 B는 최소 1 이상의 공통된 약수를 가집니다.

 

3. A= a*G , B = b*G 가 성립합니다. (G는 최대공약수)

 

4. A와 B가 최소 공배수가 되려면,

    A에는 b, B에는 a 를 곱하면 됩니다.

 

5. 하지만 a와 b는 미리 구할 수 없으므로,

    A*B/G 를 하면,

( (a*G)*(b*G) ) / G == a*b*G^/G (^는 제곱)

== a*b*G 가 성립합니다.

 

 

따라서, 최소 공배수를 구하는 공식은,

서로다른수끼리 곱한 값을 최대공약수로 나눈 값입니다.