최대공약수와 최소공배수

자연수 \(n=a\times b\)라고 한다면 \(n\)은 \(a\)의 배수, 혹은 \(b\)의 배수이다. 이때, \(a,\,b\)는 \(n\)의 인수(factor)이다. 또한 \(n\)은 \(a\)로 나누어떨어지고, \(b\)로도 나누어떨어진다. 따라서 \(a,\,b\)는 \(n\)의 약수(divisor)이다.

인수와 약수는 같은 개념으로 생각할 수도 있지만 접근법에 차이가 있다. 자연수 \(n\)을 어떤 수를 곱해서 만들었는가를 생각한다면 인수를, 어떤 수로 나눌 수 있는가를 생각한다면 약수를 이용한다. 특별히 소수인 인수를 소인수(prime factor)라고 한다.

 

자연수 \(n\)의 약수를 구할 때는 찾을 수 있는 모든 곱셈의 경우를 이용한다. 예를 들어

\[\eqalign {12&=1\times12\\&=2\times6\\&=3\times4 }\]

이므로 \(12\)의 약수는 \(1,\,2,\,3,\,4,\,6,\,12\)이다. 이 방법은 인수를 이용해서 약수를 찾았다고 할 수도 있겠다. 다음과 같이 소인수분해를 이용해서 약수를 구할 수도 있다.

 

\(12=2^2\times3\)	\(1\)	\(2\)	\(2^2\)
\(1\)	\(1\times1\)	\(1\times2\)	\(1\times2^2\)
\(3\)	\(1\times3\)	\(3\times2\)	\(3\times2^2\)

 

\(12\)의 소인수 \(2,\,3\)의 거듭제곱을 행과 열에 각각 배열하여 \(12\)를 나눌 수 있는 수를 거듭제곱의 조합을 이용해서 찾았다. 여기에서 행과 열에 \(1\)을 포함시킨 것에 주목해야 한다.

\(12\)의 약수의 개수는 (행의 개수)×(열의 개수)에서 \(2\times3=6\)이다. 소인수분해한 소인수의 거듭제곱의 지수에 \(1\)을 더한 수끼리 곱했다. 소인수가 \(3\)개 이상인 경우로 확장하면 약수의 개수를 구하는 식은 다음과 같이 정리할 수 있다.

 

\(d(n)\)을 자연수 \(n\)의 약수의 개수라 하고, \(n=p_1^a \times p_2^b \times p_3^c \times p_4^d \cdots\)

(단, \(p_1,p_2,p_3,p_4,\cdots\)는 소수)이면 

\[d(n)=(a+1)\times(b+1)\times(c+1)\times(d+1)\times \cdots\]

이다.

 

한편, 경우의 수를 이용해서 \(p_1\)에 대하여 선택하지 않는 경우를 포함하면 \((a+1)\)가지, \(p_2\)에 대하여 \((b+1)\)가지, \(p_3\)에 대하여 \((c+1)\)가지, \(p_4\)에 대하여 \((d+1)\)가지, \(\cdots\)이므로 위와 같은 식이 구해짐을 설명할 수도 있다.

 

\(6=1+2+3\)과 같이 자기 자신을 제외한 약수의 합이 자신이 되는 수를 완전수(perfect number)라고 하는데, 짝수 완전수가 무한한지는 밝혀지지 않았으며, 홀수 완전수의 존재성에 대해서도 밝혀지지 않았다. 최초 다섯 개의 완전수는 \(6,\, 28,\, 496,\, 8128,\, 33550336\)이다. 자연수 \(n\)의 약수의 합을 \(\sigma(n)\)이라고 하면 완전수는 \(\sigma(n)=2n\)이 성립하는 수이다.

 

 

자연수 n의 약수를 모두 구하는 단순 알고리즘

---

 

두 자연수 \(A,\,B\)를 동시에 나눌 수 있는 수를 공약수라고 한다. \(1\)은 모든 수의 공약수이다. 두 자연수를 동시에 나눌 수 있는 수 중에서 가장 큰 수를 최대공약수(Greatest Common Divisor)라고 한다. 최대공약수가 \(1\)인 경우 두 수는 서로소(relatively prime)라고 한다.

최대공약수를 구하는 가장 기본적인 방법은 각 수의 약수를 모두 나열한 후 그 중에서 공약수만 모아서 가장 큰 수를 찾는 것이다. 수의 특징을 활용하면 수고로움을 덜 수 있는데 소인수분해를 활용하는 것이다. 각 수를 소인수분해하면 공통인 인수를 찾을 수 있고, 이 인수들을 모두 곱한 수가 최대공약수이다. 예를 들어 \(60\)과 \(72\)의 최대공약수는

\[\eqalign{60&=\boxed{2^2 \times3} \times5 \\72&=\boxed{2^2\times3} \times2\times3}\]

혹은

\[\eqalign{2^2\times3 \;&)\underline{\;2^2\times3\times5 \qquad 2^3\times3^2}\\&\phantom{\qquad\qquad\;\;}5 \qquad2\times3}\]

이므로 \(12\)이다. 최대공약수는 공통인 인수들의 곱으로 구했으므로 최대공약수의 약수는 두 수의 공약수가 된다.

두 수를 각각 \(A=a\times G, \, B=b\times G\)(단, \(G\)는 \(A,\,B\)의 최대공약수)라 하면, \(a,\,b\)는 서로소이고, 다음과 같이 나타낼 수 있다.

\[\eqalign{G \;&)\underline{\;a\times G \qquad b\times G}\\&\phantom{\quad\;\;}a \qquad\qquad b}\]

 

소인수분해가 아닌 유클리드 호제법(Euclidean algorithm)을 이용해서 최대공약수를 구할 수 있는데 이것은 역사적으로 아주 오래된 방법이다. 기본 원리는 \(a\)와 \(b\)를 \(d\)로 나눌 수 있다면 \(a\)를 \(b\)로 나눈 나머지 \(r\)도 \(d\)로 나눌 수 있다는 것이다. 

다음의 예는 \(819\)와 \(735\)의 최대공약수 \(21\)을 유클리드 호제법을 이용하여 찾는 과정을 보여준다.

\[\eqalign{&GCD[819,735]\qquad819&=735\times1+84\\=&GCD[735,84] \qquad\;\;735&=84\times8+63\\=&GCD[84,63]\qquad\quad\;\;84&=63\times1+21\\=&GCD[63,21]\qquad\quad\;\;63&=21\times3+0\\=&GCD[21,0]&\\=&21&}\]

 

\(819=3^2\times7\times13,\, 735=3\times7^2\times5\)이므로 최대공약수는 \(3\times7=21\)임을 확인할 수 있다.

 

유클리드 알고리즘

 

세 수 \(a,\,b,\,c\)에 대한 최대공약수는 두 수 \(a,\,b\)의 최대공약수 \(d\)를 구한 후, \(c\)와 \(d\)의 최대공약수를 구하면 된다. 물론 한꺼번에 구하려고 한다면 소인수분해를 이용한 방법에서처럼 모든 수를 동시에 나눌 수 있는 수를 찾도록 한다.

 

---

공통인 배수, 즉, 공배수 중에서 가장 작은 수를 최소공배수(Least Common Multiple)라고 한다. 높이가 서로 다른 두 블록을 쌓아 올리는 경우를 상상하면 공배수와 최소공배수를 이해하기 쉽다. 예를 들어 높이가 각각 \(6\rm{cm}, 8\rm{cm}\)인 두 블록을 나란히 쌓는다고 하자. 반복해서 블록을 쌓다보면 \(6\rm{cm}\)짜리 \(4\)개, \(8\rm{cm}\)짜리 \(3\)개를 쌓으면 높이가 같아지고, 다시 쌓았던 높이만큼 쌓으면 높이가 같아진다. 이 과정을 무한히 반복할 수 있다.

 

6과 8의 최대공약수는 2이다.

 

그림에서 보듯이 최소공배수는 각각의 수의 공통인 인수와 공통이 아닌 인수를 모두 곱해서 찾을 수 있고, 최소공배수의 배수가 공배수이다. 다음은 소인수분해를 이용해서 최소공배수를 구하는 예이다. 최대공약수를 구하는 방법과 같지만, 최소공배수는 모든 인수를 포함해야 하므로 곱하는 수에 차이가 있다.

\[\eqalign{2^2\times3\times5\;) \underline{\; 2^2\times3^3\times5\qquad 2^3\times3\times5^2}\\3^2 \qquad\qquad\quad2\times5\quad}\]

따라서 두 수의 최소공배수는 \((2^2\times3\times5)\times3^2\times(2\times5) =2^3\times3^3 \times 5^2\)이다.

 

세 수의 최소공배수를 구할 때는 최대공약수를 구할 때와 차이가 있는데, 각 수의 모든 인수를 포함해야 하기 때문이다.

 

[방법1]

\[\eqalign{2^2\times3\times5 \;\underline{)\;2^2\times3\times5\qquad2^3\times3^2\qquad3\times5^2}\\1\qquad\qquad 2\times3 \qquad\qquad 5\quad}\]

[방법2]

\[{\eqalign{&2\times2&&\times5\\&2\times2\times2\times&3\times3&\\&&3&\times5\times5}}\over{2\times2\times2\times3\times3\times5\times5}\]

 

하지만 두 수의 최소공배수를 구하는 과정을 반복해서 구해도 된다. 예를 들어 \(A,\,B,\,C\)의 최소공배수를 구한다면 \(A,\,B\)의 최소공배수 \(M\)을 먼저 구하고, \(M,\,C\)의 최소공배수 \(L\)을 구하면 \(L\)은 \(A,\,B,\,C\)의 최소공배수이다.

 

두 수를 각각 \(A=a\times G, \, B=b\times G\)(단, \(G\)는 \(A,\,B\)의 최대공약수)라 하면, \(a,\,b\)는 서로소이고, 
\[\eqalign{G \;&)\underline{\;a\times G \qquad b\times G}\\&\phantom{\quad\;\;}a \qquad\qquad b}\]

이므로 최소공배수 \(L=a\times b \times G\)이고, \(A\times B= L\times G\)이다.

따라서 최소공배수를 구하는 프로그램을 작성하려고 한다면 \(L=\dfrac{A\times B}{G}\)를 이용하면 된다.