이번 시간에는 최소공배수 최대공약수 사이의 관계에 대해 학습하고 관련된 심화 문제를 풀어보기로 하자.
이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.
목차
최대공약수 최소공배수 관계
앞서 우리는 다음과 같은 최대공약수와 최소공배수에 대한 성질을 학습하였다. 이번시간에는 최대공약수와 최소공배수 사이의 관계에 대해 알아보기로하자.
- 최대공약수 $\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개이다.
이상으로 최대공약수와 최소공배수와 관련된 심화문제 풀이를 마무리 하도록 하겠다.
