[algorithm] 최대공약수(GCD)와 최소공배수(LCM) (유클리드 호제법)

최소공배수

최소공배수를 구하는 쉬운 방법은 유클리드 호제법을 사용하는 것이다.

$$ \text{유클리드 호제법}\\
\text{두 자연수 } a, b (a > b)\text{에 대하여}\\
a\text{를 } b \text{로 나눈 나머지가 }r \text{일 때}\\
a, b \text{의 최대 공약수는 }b, r \text{의 최대 공약수와 같다.}\\
\text{즉 } \gcd(a,b) = \gcd(b,r)\\
r = 0 \text{의 경우 }a,b \text{의 최대공약수는 }b \text{가 된다.}$$

 

계산과정

두 수 1568과 1260이 있을 때 두 수중 더 큰 1568을 a 1260을 b로 두고 계산한다.

1568 % 1260 = 308, 1260은 나누어 떨어지지 않음 다시 나눔

1260 % 308 = 28, 308은 나누어 떨어지지 않음 다시 나눔

308 % 28 = 11, 0 은 나누어 떨어져 r이 0이 되었기 때문에 b인 28이 최대공약수이다.

증명

$$ \text{두 자연수 }a \text{와 } b \text{가 있을 때}(a>b) \\
a/b 에서 q \text{를 몫 } r \text{을 나머지로 정의 하면} \\
r = a - bq \text{ 이다.} \\[10pt]

d = \gcd(a,b) \text{ 라고 하면 } \\
a = dx, b = dy \text{를 만족한다.}\\
(x,y \text{는 서로소}) \\[10pt]

\text{이를 } r = a-bq \text{에 대입하면} \\
r = dx - dyq \\
= d(x-yq) \\[10pt]

b = dy, r = d(x-yq) \text{이므로 } \\
d = \gcd(b,r) \text{를 만족하기 위해서는 } \\
x-yq \text{와 }y \text{가 서로소임을 증명하면 된다.} \\[10pt]
\text{만약 }  y \text{와 } x-yq \text{가 서로소가 아니라고 한다면} \\
\text{공약수 m이 존재한다.} \\
(k \text{와 } k' \text{은 서로소}) \\
y = mk \\
x-yq = mk' \\[10pt]
x = yq + mk' \\
= mkq + mk' \\
= m(kq+k') \\[10pt]

x = m(kq+k') \\
y = mk \\[10pt]
\text{이때 } m ≠ 1 \text{이라면 } x \text{와 } y \text{는 서로소라는 전제에 모순이 발생} \\
m=1 \text{라면 공약수가 } 1 \text{이 되므로 } y \text{와 } x-yq \text{가 서로소가 된다.} \\
\therefore \gcd(y,x-yq) = 1 \\[10pt]

\text{즉 } \gcd(a,b)= \gcd(b,r) \text{이 성립한다.} $$

 

 

구현

int gcd(int a, int b)
{
    //이 조건문은 이해를 돕기 위한것으로
    //while문 내부에서 a%b를 수행할 때
    //a보다 b가 더 크다면 자연스럽게 스왑이 되기에 생략이 가능하다.
    if(a < b)
    {
        int c = a;
        a = b;
        b = c;
    }

    while(b)
    {
        int left = a%b;
        a = b;
        b = left;
    }
    
    return a;
}

 

최소 공배수

최소 공배수는 최대 공약수를 사용해 간단하게 구할 수 있다.

 

계산

$$ \text{lcm}(a,b) = a * b / \gcd(a, b) $$

 

증명

$$ \text{두 자연수 } a, b \text{를 다음과 같이 표현 할 수 있다.} \\
a = \gcd(a, b) * x \\
b = \gcd(a, b) * y \\
\text{이 때 } x \text{와 } y \text{는 서로소이다.} \\[10pt]
\gcd(a, b) \text{를 } d \text{라 하면} \\
a = d * x \\
b = d * y \\[10pt]
\text{즉 } a*b = d * x * d * y = d^2 * x * y \\
x \text{와 } y \text{는 서로소이기 때문에 lcm}(x,y) = x*y \\
\text{따라서 최소 공배수는 다음과 같이 정의된다.} \\
\text{lcm}(a, b) = d * x * y = \frac{d^2 * x * y}{d} = \frac{a * b}{d} = \frac{a*b}{\gcd(a,b)} $$

 

구현

int lcm(int a, int b)
{
    return a * b / gcd(a,b);
}