이번 시간에는 최소공배수 최대공약수 사이의 관계에 대해 학습하고 관련된 심화 문제를 풀어보기로 하자.
개요
최대공약수 최소공배수 관계
앞서 우리는 다음과 같은 최대공약수와 최소공배수에 대한 성질을 학습하였다. 이번시간에는 최대공약수와 최소공배수 사이의 관계에 대해 알아보기로하자.
- 최대공약수 $\xrightarrow[]{\text{약수}}$ 공약수
- 최소공배수 $\xrightarrow[]{\text{배수}}$ 공배수
두 수의 최대공약수와 최소공배수 관계
다음 예를 통해 두 수의 최대공약수(G)와 최소공배수(L) 사이의 관계에 대해 정리해 보자. ( G: greatest common divisor, L:least common multiple의 약자 )
두 수 $A=12,\;B=30$의 최대공약수 $G$, 최소공배수 $L$에 대하여
$\begin{aligned}
\bbox[#ffff00]{6} \: \underline{)\;12\qquad30}\\
\bbox[#94feff]{2}\qquad\;\;\bbox[#94feff]{5}\\
\end{aligned}$
$2,5: \text{ 서로소}$
$G=\bbox[#ffff00]{6} ,\qquad L=\bbox[#ffff00]{6} \times2\times5$
$A=\bbox[#ffff00]{6}\times2,\qquad B=\bbox[#ffff00]{6}\times5$
$G\times L=\bbox[#ffff00]{6}\times2\times\bbox[#ffff00]{6}\times5=A\times B$
이와 같은 사실을 정리하면 다음과 같다.
두 수 $A,\;B$의 최대공약수 $G$, 최소공배수 $L$에 대하여
$\begin{aligned}
\bbox[#ffff00]{G} \: \underline{)\;A\qquad B}\\
\bbox[#94feff]{a}\qquad\;\;\bbox[#94feff]{b}\\
\end{aligned}$
$a,b:\text{ 서로소}$
$L=\bbox[#ffff00]{G} \times a\times b$
$G\times L=\bbox[#ffff00]{G}\times a\times \bbox[#ffff00]{G}\times b=AB$
$\qquad \therefore \;G\times L= A\times B$
심화 문제
[1] 두 자연수 $A,\; B$에 대하여 $A\times B=720$이고 두 수의 최소공배수 $L=180$일 때 가장 큰 $A+B$의 값을 구하여라.
[풀이]
최대공약수 G에 대하여
$A \times B=G\times L=G\times 180=720$
$G=720\div180=4$ 이고 따라서
$\begin{aligned}
\bbox[#ffff00]{4} \: \underline{)\;A\qquad B}\\
\bbox[#94feff]{a}\qquad\;\;\bbox[#94feff]{b}\\
\end{aligned}$
서로소인 몫 $a,b$를 생각 할 수있다.
$(a\times b)\times \bbox[#ffff00]{4} =180$이고
$a\times b=180\div4=45=3^2\times5$이다.
서로소인 두 수를 곱하여 45가 되는 경우를 살펴보자.
$a,\;b$가 서로소 이므로 두 수의 공통인수가 생기지 않아야 한다. 이를 쉽게 생각하기 위해 위의 식에서 처럼 45를 공통소인수가 한눈에 보이도록 소인수분해 하여 정리 하였다.
$a$에 들어올 자연수 또한 소인수분해로 생각하면 $a,b$ 자리에 $9,5$를 생각할 수있다. 이때 주의할 점은 자연수 $1$은 소수도 합성수도 아니므로, 소인수 분해로 생각할 수 없기 때문에 따로 고려해야 한다는 점이다. 이를 정리하면 다음과 같다.
$a \text{자리}\begin{cases} \text{소인수 분해가 되지 않는 수} : \bbox[#ffff00]{1}\\[1em]
\text{소인수 분해 되는 수}\begin{cases}\bbox[#94feff]{\text{소인수 1개}}\\\bbox[#ffc5fd]{\text{소인수 2개}}\\ \cdots \end{cases} \\
\end{cases}$
$\bbox[#ffff00]{1},\;45\xrightarrow{\times4\;} A+B=1\times4+45\times4=184$
$\bbox[#94feff]{9},\;5\xrightarrow{\times4\;} A+B=9\times4+5\times4=56$
$\bbox[#ffc5fd]{45},\;1\xrightarrow{\times4\;}A+B=45\times4+1\times4=184$
$A+B$의 값을 구하는 문제 이므로 소인수가 2개인 마지막 경우는 첫 번째 경우로 다루었으므로 생략해도 무방하다. 따라서 $A+B$는 두 값을 가지고, 최댓값은 184이다.
[2] 두 자연수 $A,\; B$에 대하여 두 수의 최대공약수 $G=4$ 최소공배수 $L=120$일 때 $A+B$의 값을 모두 구하여라.
[풀이]
두 수 $A,\;B$에 대하여
$\begin{aligned}
\bbox[#ffff00]{4} \: \underline{)\;A\qquad B}\\
\bbox[#94feff]{a}\qquad\;\;\bbox[#94feff]{b}\\
\end{aligned}$
서로소인 몫 $a,b$를 생각 할 수있다.
$(a\times b)\times \bbox[#ffff00]{4} =120$이고
$a\times b=120\div4=30=2\times 3\times 5$이다.
서로소인 두 수를 곱하여 $30$이 되는 경우를 정리하는 과정은 다음과 같다.
$a \text{자리}\begin{cases} \text{소인수 분해가 되지 않는 수} : \bbox[#ffff00]{1}\\[1em]
\text{소인수 분해 되는 수}\begin{cases}\bbox[#94feff]{\text{소인수 1개}}\\\bbox[#ffc5fd]{\text{소인수 2개}}\\ \cdots \end{cases} \\
\end{cases}$
$\bbox[#ffff00]{1},\;30\xrightarrow{\times4\;} A+B=1\times4+30\times4=124$
$\bbox[#94feff]{2},\;15\xrightarrow{\times4\;} A+B=2\times4+15\times4=68$
$\bbox[#94feff]{3},\;10\xrightarrow{\times4\;} A+B=3\times4+10\times4=52$
$\bbox[#94feff]{5},\;6\xrightarrow{\times4\;} A+B=5\times4+6\times4=44$
$\bbox[#ffc5fd]{30},\;1\xrightarrow{\times4\;} A+B=30\times4+1\times4=124$
$A+B$ 값을 구하는데 있어 소인수가 2개인 경우는 첫 번째와 동일한 결과이다. 따라서 마지막 과정은 생략 할 수 있다.
따라서 $A+B$의 값은 $44,\; 52,\;68,\;124$이다.
소인수분해, 최대공약수 최소공배수
소인수분해를 이용한 최대공약수와 최소공배수를 구하는 방법에 대해 다시 정리하고 문제를 풀어보자.
거듭제곱을 이용한 최대공약수, 최소공배수
- 소인수분해 $\rightarrow$ 거듭제곱 표현
- $\begin{cases}\text{최대공약수: }\bbox[yellow]{\text{공통 소인수}}^\bbox[cyan]{\text{최소지수}}\text{의 곱}\\[1em]
\text{최소공배수: }\bbox[yellow]{\text{모든 소인수}}^\bbox[cyan]{\text{최대지수}}\text{의 곱}\\[1em]
\end{cases}$
이를 적용하여 다음 응용문제를 풀어보자.
[1] 세 자연수 $30,\;75,\;N$의 최대공약수 $G=15$이고, 최소공배수 $L=450$ 일 때 $N$의 개수를 구하여라.
[풀이]
주어진 자연수와 최대공약수,최소공배수를 소인수분해 하고 $N$의 소인수와 지수에 대해 생각해 보면 다음과 같다.
$\begin{align}
30=&2^1\;\times\;3^1\;\times\;5^1\\
75=&\;\bbox[#ffff00]{1}\,\;\times\;3^1\;\times\;5^2\\
N=&\triangle\;\times\,\square\;\,\times\,\bigcirc\\
\hline
L=450=&2^1\;\times\;3^2\;\times\;5^2\\
G=\;15=&\;\bbox[#ffff00]{1}\,\;\times\;3^1\;\times\;5^1\\
\end{align}$
곱셈으로 연결되어 있으므로, 비어있는 자리를 $\bbox[#ffff00]{1}$로 채우고 생각하면 편하다. 최대공약수와 최소공배수의 거듭제곱은 다음 두 가지 거듭제곱으로 구성된다.
$\bbox[yellow]{\text{공통 소인수}}^\bbox[cyan]{\text{최소지수}}\text{의 곱}$
$\bbox[yellow]{\text{모든 소인수}}^\bbox[cyan]{\text{최대지수}}\text{의 곱}$
따라서 이 들은 반드시 세 숫자의 거듭제곱에 적어도 한 번 있어야 한다. $3^2$이 주어진 두 숫자 없기 때문에 $\square$의 자리는 반드시 $3^2$이 와야 한다.
나머지 자리는 최대공약수와 최소공배수를 고려해 최소지수, 최대지수를 범위를 벗어나지 않는 거듭제곱이 올 수있다.
- $\triangle$ : $1$(최대공약수), $2^1$(최소공배수)
- $\bigcirc$ : $5^1$(최대공약수), $5^2$(최소공배수)
따라서 $N$은 4개 값을 가질 수있다.
[2] 다음은 세 자연수 $A,\;B,\;N$와 세 수의 최대공약수 $G$, 최소공배수$L$을 각 각 소인수분해하여 정리한 결과이다. $N$의 값의 개수를 구하여라.
$\begin{align}
A=&2^1\;\times\;3^2\;\times\;5^3\;\times\;7^3\\
B=&2^1\;\times\;3^2\;\times\;\quad\,\;\times\;7^2\\
N=&\triangle\;\times\,\square\,\;\times\,\bigcirc\,\;\times\,\lozenge\\
\hline
L=&2^2\;\times\;3^2\;\times\;5^3\times\;7^3\\
G=&2^1\;\times\;3^1\\
\end{align}$
[풀이]
먼저 비어있는 자리를 ${\color{#dc143c}1}$로 채우면 다음과 같다.
$\begin{align}
A=&\bbox[#ffff00]{2^1}\;\times\;\bbox[#ffff00]{3^2}\;\times\;\bbox[#ffff00]{5^3}\;\times\;\bbox[#ffff00]{7^3}\\
B=&2^1\;\times\;3^2\;\times\;\bbox[#ffff00]{{\color{#dc143c}1}}\,\;\times\;7^2\\
N=&\triangle\;\times\,\square\;\times\,\bigcirc\;\times\,\lozenge\\
\hline
L=&\bbox[#ffff00]{2^2}\;\times\;\bbox[#ffff00]{3^2}\;\times\;\bbox[#ffff00]{5^3}\times\;\bbox[#ffff00]{7^3}\\
G=&\bbox[#ffff00]{2^1}\;\times\;\bbox[#ffff00]{3^1}\;\times\;\bbox[#ffff00]{{\color{#dc143c}1}}\;\,\times\;\bbox[#ffff00]{{\color{#dc143c}1}}\\
\end{align}$
최대 공약수와 최소공배수의 거듭제곱중 두 수에 존재하지 않는 것은 반드시 $N$의 인수로 존재해야 한다.
- $\triangle=2^2,\;\square=3^1,\;\lozenge=1$
$5$의 거듭제곱 자리($\bigcirc$)에는 최소지수(최대공약수)와 최대지수(최소공배수)를 벗어나지 않는 거듭제곱이 전부 올 수 있다.
- $\bigcirc=\bbox[#ffff00]{1},\;5,\;5^2,\;\bbox[#ffff00]{5^3}$
따라서 $N=\triangle\times\square\times \bigcirc\times \lozenge$의 개수는 4개이다.
이상으로 최대공약수와 최소공배수와 관련된 심화문제 풀이를 마무리 하도록 하겠다.