최대공약수 구하기 소인수분해 이용

이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.

공약수와 최대공약수

소인수분해를 이용한 최대공약수와 공약수를 구하는 방법에 대해 학습하기 전에 초등학교에서 배운 개념과 서로소에 대한 개념을 정리하도록 하자.

정의

공약수: 두 개 이상의 자연수의 공통 약수
최대공약수: 공약수 중에서 가장 큰 수
서로소: 최대공약수가 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{최소지수}}$의 곱
공약수: 최대공약수의 약수

공약수는 최대공약수의 약수