1 최대공약수

최대공약수(GCD, Greatest Common Divisor)는 공약수 가운데 가장 큰 수다. 예를 들어, 두 자연수 $n$, $m$이 있다고 가정하고 두 수의 최대공약수를 찾아보자. 먼저, 두수를 소인수 분해를 하여 나타낸다. 두 수를 곱했을 때 각 소수별 가장 작은 승수를 찾아 조합하면 된다.

$n = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$
$m = p_1^{f_1} p_2^{f_2} \cdots p_t^{f_t}$
$\gcd\{n,m\} = p_1^{\min\{e_1,f_1\}} p_2^{\min\{e_2,f_2\}} \cdots p_t^{\min\{e_t,f_t\}}$

추가로, 최대공약수와 최소공배수는 다음 관계를 갖는다.

\[\gcd\{n,m\} = \frac{n \times m}{\operatorname{lcm}\{n,m\}}\] 두 수 192와 72의 최대공약수를 소인수 분해 방법을 통해 구해보자.

$192 = 2^6 \times 3^1$
$72 = 2^3 \times 3^2$
$\gcd\{192, 72\} = 2^{\min\{6, 3\}} \times 3^{\min\{1, 2\}} = 2^3 \times 3^1 = 8 \times 3 = 24$

1.1 유클리드 호제법

소인수 분해 방법 말고 유클리드 호제법(Euclidean algorithm)을 사용해서 똑같이 두 수 192와 72의 최대공약수를구하여 보자. 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 먼저 두 수 중에서 작은 수로 큰 수를 나눈다.

일단 192을 72로 나누어 나머지를 구한다. 이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다.
- $192 = 72 \times 2 + 48$
이번에는 72을 나머지인 48로 나눈다.
- $72 = 48 \times 1 + 24$
이와 같은 연산을 나머지가 0이 될 때까지 반복한다.
- $48 = 24 \times 2 + 0$
나머지가 0이 되었으므로 연산을 중지한다. 이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다. 즉, 24가 두 수 192와 72의 최대공약수가 된다.

상기 알고리즘을 R코드로 작성하면 다음과 같다.

euclid_gcd <- function(n, m) {
  if(n < m) {
    stop("n, m 두 숫자 순서를 바꿔 입력하세요.")
  }
  while(m > 0) {
    temp <- m
    m <- n %% m
    n <- temp
  }
  return(n)
}
# gcd(72, 192)
# Error in gcd(72, 192) : n, m 두 숫자 순서를 바꿔 입력하세요.

euclid_gcd(192, 72)

[1] 24

numbers 팩키지 extGCD() 함수는 확장된 유클리드 알고리즘으로 최대공약수를 계산할 뿐만 아니라 최대공약수를 두수를 선형결합으로 표현할 수 있게 해준다. 즉, $a, b$는 최대공약수를 구하게 되면 2원 1차 연립방정식을 세울 수 있어 쉽게 구할 수 있다.

$\gcd\{n,m\} = a \times n + b \times m$
$24 = (-1) * 192 + 3 * 72$

library(numbers)

numbers::extGCD(192, 72)

[1] 24 -1  3

2 최소공배수

최소공배수(LCM, Least Common Multiple)은 양의 공배수 가운데 가장 작은 수를 의미하며, 분수끼리 더하거나 뺄 때 사용되는 통분이 가장 흔히 사용되는 응용으로 볼 수 있다. 통분 과정에서 최소공분모(분모의 최소공배수)를 계산하게 되면 쉽게 통분을 할 수 있다.

\[\frac{2}{21} + \frac{1}{6} = \frac{4}{42} + \frac{7}{42} = \frac{11}{42}\]

$21$, $6$을 인수분해한다.
- $21 = 3 \times 7$
- $6 = 2 \times 3$
$21$, $6$의 최대공약수를 구한다.
- $\operatorname{gcd}(21, 6) = 3$
최소공배수를 구한다.
- $\operatorname{gcd}(21, 6) \times 2 \times 7 = 42$

여기서, 최대공약수와 최소공배수 다음 성질을 이용한다.

$n = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$
$m = p_1^{f_1} p_2^{f_2} \cdots p_t^{f_t}$
$\gcd\{n,m\} = p_1^{\max\{e_1,f_1\}} p_2^{\max\{e_2,f_2\}} \cdots p_t^{\max\{e_t,f_t\}}$

최소공배수를 활용한 사례를 알아보자.¹

어느 버스 종점에서 신촌역으로 가는 버스는 2분, 시청으로 가는 버스는 3분마다 출발한다고 가정하자. 9시에 동시에 출발했을 때 9시 이후 동시에 다시 출발하는 시간을 구해보자.

버스: 9시, 9시 2분, 9시 4분, 9시 6분 …
기차: 9시, 9시 3분, 9시 6분 …

$\text{lcm}(\text{2}, \text{3}) = 6$

3 연분수

연분수(Continued Fraction)는 다음과 같은 모양을 갖는 분수를 말한다. 유리수는 유현 연분수로 무리수는 무한 연분수로 표현할 수 있고, 유리수를 연분수로 고치는 대표적인 유클리드 호제법이다.

\[x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3+\,\ddots}}}\] 두 수 192와 72의 최대공약수를 구한 사례를 연분수로 나타내 보자. 몫과 나머지로 나눈다. 그리고 나서 나머지를 뒤집는다. 그러면 나머지의 분모를 다시 나눌 수가 있게 되고 이 과정을 반복하여 더이상 나눠지지 않을 때까지 반복한다.

$$ \[\begin{array}{rl} \frac{192}{72} =& 2 + \frac{48}{72} \\ =& 2 + \frac{1}{\frac{72}{48}} \\ =& 2 + \frac{1}{1+ \frac{24}{48}} \\ =& 2 + \frac{1}{1+ \frac{1}{\frac{48}{24}}} \\ =& 2 + \frac{1}{1+ \frac{1}{2}} \end{array}\]

ZUM 학습백과, “최소공배수의 활용”↩︎

데이터 과학자 이광춘 저작

kwangchun.lee.7@gmail.com

기호 수학(Symbolic Math)

최대공약수

이광춘

2021-02-12

1 최대공약수

1.1 유클리드 호제법

2 최소공배수

3 연분수