유클리드 알고리즘: 최대공약수 구하기

이 글의 목차

인터랙티브

나머지가 0이 될 때까지 (a, b)를 (b, a mod b)로 바꾼다

나누기자동초기화

a

252

b

105

나눗셈 과정

#	a	b	q	r

나누기를 눌러 첫 나눗셈을 실행하세요.

a = q·b + r, 0 ≤ r < b · gcd(a, b) = gcd(b, r)

입력이 커지면 약수를 하나씩 확인해 최대공약수를 구하기 어렵다. 유클리드 알고리즘은 공약수를 보존하면서 두 수를 더 작은 쌍으로 바꾸고, 답이 드러날 때까지 반복한다. 여기서는 비음수 정수에 대해 $\gcd(0,0)=0$으로 정한다.

쌍을 바꾸어도 최대공약수가 같은 이유

$b>0$인 비음수 정수 $a,b$에 대해 유클리드 나눗셈으로 유일한 정수 $q,r$를 정할 수 있다.

$a=bq+r,\qquad 0\le r<b.$

그러면

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

$a,b$를 모두 나누는 정수는 $a-bq=r$도 나눈다. 반대로 $b,r$을 모두 나누는 정수는 $bq+r=a$도 나눈다. 따라서 두 쌍의 공약수는 정확히 같고, 최대 비음수 공약수도 같다.

계산 과정과 종료

$252$와 $105$에 적용하면 다음 나눗셈을 얻는다.

$252=2\cdot105+42,\qquad105=2\cdot42+21,\qquad42=2\cdot21+0.$

매 단계에서 최대공약수가 보존되므로

$\gcd(252,105)=\gcd(105,42)=\gcd(42,21)=\gcd(21,0)=21.$

나머지가 양수이면 직전의 제수보다 작다. 따라서 비음수 나머지는 엄격히 감소하다가 반드시 0이 된다. 마지막으로 0이 아닌 값이 최대공약수다. 모든 비음수 $a$에 대해 $\gcd(a,0)=a$이며, 이 규약은 $\gcd(0,0)=0$도 포함한다.

두 입력이 양수일 때 나눗셈 횟수는 $O(\log\min(a,b))$이다. 가장 느린 경우에도 나머지들이 연속한 피보나치 수 크기로 줄어들므로 두 단계마다 작은 입력이 일정한 비율로 감소한다. 이는 정수 연산 횟수에 대한 분석이며, 임의로 큰 정수의 비트 연산 비용까지 나타내지는 않는다.

반복형 C++ 구현

다음 함수는 int로 표현 가능한 비음수 int만 받는다. 음수 입력에서 C++ 나머지 연산에 의존하지 않도록 이 전제 조건을 둔다. 함수는 비음수 최대공약수를 반환하며 gcd(0, 0) == 0이다.

int gcd(int a, int b) {
    // 전제 조건: a >= 0, b >= 0.
    while (b != 0) {
        int remainder = a % b;
        a = b;
        b = remainder;
    }
    return a;
}

매 반복에서 remainder는 $a=bq+r$의 $r$이며, 쌍이 $(b,r)$로 바뀌어도 최대공약수는 변하지 않는다. b가 0이 되면 a가 답이다.