[백준 2609] 최대공약수와 최소공배수

최대공약수와 최소공배수 구하기

일반적으로 교과과정에서 배운 최대공약수 구하는 법은
두 수를 2나 3, 나뉠만한 소수로 계속 나눠보는 것이다.

 

gcd와 lcm 구하기

위와 같이 더이상 나눠지지 않는 수까지 나눈 후에,
즉 A와 B를 서로소가 될 때까지 나눈 후에
왼쪽 나눈 수들을 전부 곱한 값이 gcd, 최대공약수이고
A, B를 gcd로 나눈 몫들을 모두 gcd와 곱한 값을 lcm, 최소공배수라 한다.

최대공약수 gcd = greatest common divisor
최소공배수 lcm = least common multiple

이는 사실 A와 B를 소인수분해한 후, 공통약수를 모두 골라내는 작업과 같다.
하지만 이 계산법들은 A와 B가 커질수록 소인수분해하기 어려워진다.

유클리드 호제법: Euclidean algorithm

원이름은 유클리드 알고리즘.
호제라는 뜻은 서로(호) 나눈다(제)는 뜻이고,
이 알고리즘을 적용하는 방법 때문에 붙인 이름인 듯 하다.

두 양의 정수 $a,b (a>b)$에 대하여 $a=bq+r,(0\le r<b) $ 일 때,
$a,b$의 최대공약수는 $b,r$의 최대공약수와 같다.

$$gcd(a, b)=gcd(b, r)$$

$r=0$이라면, $a,b$의 최대공약수는 $b$가 된다.

증명

증명을 한 번 하고나면, 조금 더 직관적으로 와닿는다.

$gcd(A,B)=g$일 때, $gcd(B,r)=g$임을 증명하자.

$A$와 $B$의 최대공약수가 $g$일 때, 더 큰 수 $A$를 $B$로 나누면 $A=Bq+r$로 표현된다.
($r$은 나누는 수 $B$보다 작으므로 $0\le r\lt B$이다.)

$gcd(A,B) = g$이므로, A와 B를 아래와 같이 표현 가능하다.
$$A=ga\newline B=gb\newline gcd(a,b)=1$$
$gcd(a,b)=1$는 $a$와 $b$가 서로소임을 뜻한다.

$A$를 $B$로 나눈 $A=qB+r$에서 $A=ga, B=gb$를 대입하면 $ga = q(gb)+r$이 되고
$r$에 대해서 $r=g(a-qb)$로 정리된다.
말인즉슨, $r'=a-qb$으로 놓으면
$$r=gr'$$
$r$이 $g$로 나누어진다.

보이고자 하는 것은 $gcd(B,r)=g$이다.
처음에 $B=gb$로 놓았었고 이제 $r=gr'$을 얻었으므로
$B$와 $r$이 모두 공통인수 $g$를 갖는것을 확인했다.

이에 더해 $b$와 $r'$이 서로소, 즉 $gcd(b,r')=1$이라면, $gcd(B,r)=g$가 된다.

$gcd(r',b)=1$임을 보여야 하므로,
$gcd(r',b)=\alpha$, $(\alpha\neq 1)$으로 가정해보자. (귀류법)
그럼 이렇게 된다. $r'=\alpha r''$, $b=\alpha b'$

$A$와 $B$에 대해서 식을 정리하면,
$A=qB+r=q(gb)+gr'=qg(\alpha b')+g(\alpha r'')=g\alpha(qb'+r'')$
$B=gb=g(\alpha b')$

즉 $A$와 $B$가 모두 $g\alpha$의 공약수를 갖게된다.
이는 처음 가정이었던 $gcd(A,B)=g$에 모순이므로
귀류법에의해 $gcd(r',b)=1$이다.

결론적으로 $B=gb$, $r=gr'$이고 $gcd(r',b)=1$이므로
$B$와 $r$또한 최대공약수 $g$를 갖는다는것이 증명되었다.

백준 2609: 최대공약수와 최소공배수

#include<cstdio>
int Euclidean(int a, int b) {
    int r = a%b;
    if(r==0) { // meaning that a is dividable by b
        return b;
    }
    return Euclidean(b,r);
}
int main() {
    int a,b;
    scanf("%d %d", &a, &b);
    int gcd = Euclidean(a,b);
    printf("%d\n%d", gcd, a*b/gcd);
}