Euclidean Algorithm - 유클리드 호제법

# Definition

$ a = bq + r(0 \le r < b) $ $\Rightarrow $ $GCD(a, b) = GCD(b, r)$

---

최대공약수에 관한 문제에서 자주 쓰이는 기본 정리 중 하나이다.

증명부터 해보자.

 

$ Lemma 1)$ $WLOG \ a >= b,$ $GCD(a, b) = GCD(a-b, b) $

---

$g=GCD(a,b),$ $ \ a = gA,$ $ \ b =gB$ 라 두자.

$ GCD(a-b, b) $ $= GCD(g(A-B), gB) $ 이기에 A-B와 B가 서로소임을 보이면 Lemma 1은 증명된다.

귀류법으로

$ GCD(A-B, B) = g_{A,B},$ $A-B = g_{A,B}M,\ B $ $= g_{A,B}N,\ g_{A,B} \neq 1$ 를 만족하는

$\exists g_{A,B} \in \mathbb{Z} $가 존재한다고 가정하자.

$ B = g_{A,B}N,$ $A = (A-B) + B = g_{A,B}M + g_{A,B}N $ $= g_{A,B}(M+N) $

$ a = gA $ $= gg_{A,B}(M+N),$ $ b = gB =$ $ gg_{A,B}N $으로 부터

$ g = GCD(a, b) $ $= \geq gg_{A,B} $

$ g_{A,B} \le 1 $ 

이는 가정과 모순됨으로 Lemma 1이 증명된다.

 

이제 Lemma 1으로부터 본 정리가 증명됨은 자명하다.

 

$WLOG\ a=bq+r(0 \le r < B) $ 이라 두자.

$ GCD(a, b) = GCD(a - b, b) $ $= GCD(a - 2b, b) = \cdots $ $= GCD(a - bq, b) = GCD(r, b) $ $= GCD(b, r) $

을 얻을 수 있음을 확인 할 수 있다.

 

# Pseudo Code

유클리드 호제법을 이용한 최대공약수를 구하는 코드는 다음과 같이 간결하게 쓸 수 있다.

int gcd(int a, b) {
  if(b == 0) return a;
  return gcd(b, a%b);
}