개요
공약수와 최대공약수
소인수분해를 이용한 최대공약수와 공약수를 구하는 방법에 대해 학습하기 전에 초등학교에서 배운 개념과 서로소에 대한 개념을 정리하도록 하자.
정의
- 공약수: 두 개 이상의 자연수의 공통 약수
- 최대공약수: 공약수 중에서 가장 큰 수
- 서로소: 최대공약수가 1뿐인 두 자연수
예시
12, 30의 최대공약수
$12$의 약수: $\{1,2,3,4,6,12\}$
$30$의 약수: $\{1,2,3,5,6,10,15,30\}$
$12$와 $30$의 공약수: $\{1,2,3,6\}$
$12$와 $30$의 최대공약수: $\{6\}$
14, 15의 최대공약수
$14$의 약수: $\{1,2,7,14\}$
$15$의 약수: $\{1,3,5,15\}$
$14$와 $15$의 공약수: $\{1\}$
$14$와 $15$의 최대공약수: $\{1\}$
$\therefore$ $14$ 와 $15$는 서로소이다.
성질
- 공약수는 최대공약수의 약수이다.
위의 성질을 수학적으로 정리하면 다음과 같다.
최대공약수가 $d$인 두 수 $A,B$의 공약수 $c$에 대하여
- $c$는 $d$의 약수이다.
이 사실에 대한 증명은 유클리드 알고리즘에 기반한 증명으로 대학교 수준이다. 사실에 대한 예를 통해 간단히 확인하는 정도로 넘어가길 바란다. 증명은 이 글의 마지막 부분에 정리해 두도록 하겠다.
최대공약수를 구하는 방법
나눗셈을 이용하는 방법(초등학교)
초등학교에서 배운 최대 공약수를 구하는 방법을 다시 한번 정리해 보자.
- 두 몫이 $\bbox[cyan]{\text{서로소}}$가 될 때까지 $1$이 아닌 $\bbox[yellow]{\text{공약수}}$로 나눈다
- 최대공약수: 공약수를 모두 곱한 수
두 수의 최대공약수
$12$와 $30$의 최대공약수는 다음과 같이 구할 수 있다.
$\begin{aligned}
\bbox[yellow]{2} \: \underline{)\;12\qquad30}\\
\bbox[yellow]{3} \: \underline{)\;\;\;6\qquad15}\\
\bbox[cyan]{2}\qquad\;\;\bbox[cyan]{5}
\end{aligned}$
$\bbox[cyan]{2},\bbox[cyan]{5}$의 최대공약수: $1$ (서로소)
$12,30$의 최대공약수 : $\bbox[yellow]{2} \times \bbox[yellow]{3}=6$
세 수의 최대공약수
- 세 몫의 $\bbox[cyan]{\text{최대공약수가 1}}$이 될 때까지 $1$이 아닌 $\bbox[yellow]{\text{공약수}}$로 나눈다
- 최대공약수: 공약수를 모두 곱한 수
위와 같은 과정으로 $24,36,60$의 최대 공약수는 다음과 같이 구할 수 있다.
$\begin{aligned} \bbox[yellow]{2} \: \underline{)\:24\qquad36\qquad60\:}\\ \bbox[yellow]{2} \: \underline{)\:12\qquad18\qquad30\:}\\
\bbox[yellow]{3}\: \underline{)\;\:\:6\qquad\;\;9\qquad15\:}\\
\;\:\:\bbox[cyan]{2}\qquad\;\;\bbox[cyan]{3}\qquad\;\;\bbox[cyan]{5}\:
\end{aligned}$
$\bbox[cyan]{2},\bbox[cyan]{3},\bbox[cyan]{5}$의 최대 공약수: $1$
$24,36,60$의 최대공약수 : $\bbox[yellow]{2}\times \bbox[yellow]{2}\times \bbox[yellow]{3}=12$
소인수분해를 이용하는 방법(중학교)
이 과정을 더 쉽게 수행하기 위해 $12,30$의 소인수를 순서대로 풀어 적고 같은 소인수끼리 줄을 맞추면 최대 공약수는 공통인 소인수만 골라 최대공약수를 계산할 수 있다.
$\begin{align}
12=&\bbox[yellow]{2}\;\times\;2\;\times\;\bbox[yellow]{3}\\
30=&\bbox[yellow]{2}\qquad\;\;\times\;\bbox[yellow]{3}\;\times\;5\\
\hline
&\bbox[yellow]{2}\qquad\;\;\times\;\bbox[yellow]{3}
\end{align}$
$\therefore$ 최대공약수 : $2\;\times\;3$
비슷한 방법으로 $24,36,60$의 최대공약수도 다음과 같이 구할 수 있다.
$\begin{align}
24=&\bbox[yellow]{2}\;\times\;\bbox[yellow]{2}\;\times\;2\;\times\;\bbox[yellow]{3}\\
36=&\bbox[yellow]{2}\;\times\;\bbox[yellow]{2}\;\qquad\;\times\;\bbox[yellow]{3}\;\times\;3\\
60=&\bbox[yellow]{2}\;\times\;\bbox[yellow]{2}\;\qquad\;\times\;\bbox[yellow]{3}\;\qquad\;\times\;5\\
\hline
&\bbox[yellow]{2}\;\times\;\bbox[yellow]{2}\;\qquad\;\times\;\bbox[yellow]{3}
\end{align}$
$\therefore$ 최대공약수 : $2\;\times\;2\;\times\;3$
규칙성 정리
이 결과를 거듭제곱을 이용해 정리해 보고 규칙성을 찾아 일반화 하여 정리하기로 하자.
$\begin{align}
24=&\bbox[yellow]{2}^3\;\times\;\bbox[yellow]{3}^\bbox[cyan]{1}\\
36=&\bbox[yellow]{2}^\bbox[cyan]{2}\;\times\;\bbox[yellow]{3}^2\\
60=&\bbox[yellow]{2}^\bbox[cyan]{2}\;\times\;\bbox[yellow]{3}^\bbox[cyan]{1}\;\times\;5\\
\hline
&\bbox[yellow]{2}^\bbox[cyan]{2}\;\times\;\bbox[yellow]{3}^\bbox[cyan]{1}
\end{align}$
$\therefore$ 최대공약수 : $2^2\;\times\;3$
공약수와 최대공약수 구하기
소인수 분해를 이용해 최대공약수와 공약수를 구하는 방법은 다음과 같다.
- 소인수 분해 $\rightarrow$ 거듭제곱 표현
- 최대공약수: $\bbox[yellow]{\text{공통 소인수}}^\bbox[cyan]{\text{최소지수}}$의 곱
- 공약수: 최대공약수의 약수
공약수는 최대공약수의 약수
최대공약수가 $d$인 두 수 $A,B$의 공약수 $c$에 대하여
- $c$는 $d$의 약수이다.
증명
- $\exists \;x,y \in \mathbb{Z}\;\;s.t. \;Ax+By=d$
- $c|\bbox[#ffff00]{A},\;c|\bbox[#ffff00]{B}$이면 $\exists a,b \in\mathbb{N}\;\; st. A=ac,B=bc$
- $d=Ax+By=acx+bcy=c(ax+by)$
$c>0,d>0$ 이므로 $(ax+by)>0$ - $\therefore\;c|d$ 이다.$_\square$
이상으로 최대공약수에 관한 학습을 마무리 하도록 하겠습니다.