최대공약수와 유클리드 호제법

두 수의 최대공약수를 소인수분해 없이 빠르게 구하는 방법이 유클리드 호제법이다. 기원전 300년경의 알고리즘이지만 지금도 컴퓨터 암호에서 매일 쓰인다. 호제법을 거꾸로 따라가면 베주 항등식이 나온다.

핵심 개념

  • $\gcd(a,b)$: 공약수 중 가장 큰 수, $\operatorname{lcm}(a,b)$: 공배수 중 가장 작은 수
  • $\gcd(a,b)=1$이면 서로소
  • $\gcd(a,b)\times\operatorname{lcm}(a,b)=ab$

핵심 정리

  • 유클리드 호제법: $a=bq+r$이면 $\gcd(a,b)=\gcd(b,r)$
  • 베주 항등식: $ax+by=\gcd(a,b)$를 만족하는 정수 $x,y$가 존재한다.
21×8 직사각형을 가능한 큰 정사각형으로 채워 나간 그림
직사각형에서 가장 큰 정사각형을 잘라 내는 과정이 호제법이다. 마지막 정사각형의 한 변이 최대공약수이다
증명 보기

호제법. $d$가 $a$와 $b$의 공약수이면 $r=a-bq$도 $d$로 나누어떨어지므로 $d$는 $b$와 $r$의 공약수이다. 거꾸로 $b$와 $r$의 공약수는 $a=bq+r$을 나누므로 $a$와 $b$의 공약수이다. 공약수의 집합이 같으므로 최대공약수도 같다. 나머지는 매번 줄어들므로 언젠가 $0$이 되고, 그 직전의 나머지가 최대공약수이다.

베주 항등식. $ax+by$ ($x,y$는 정수) 꼴의 양수 중 가장 작은 것을 $s$라 하자. $a$를 $s$로 나누면 $a=sq+r$ ($0\le r<s$)이고 $r=a-sq$도 $ax+by$ 꼴이다. $s$가 가장 작은 양수이므로 $r=0$, 즉 $s\mid a$이다. 같은 방법으로 $s\mid b$이다. 따라서 $s\le\gcd(a,b)$이다. 한편 $\gcd(a,b)$는 $a$와 $b$를 나누므로 $s=ax+by$도 나누어 $\gcd(a,b)\le s$이다. 따라서 $s=\gcd(a,b)$이다. $\blacksquare$

예제

$\gcd(252,198)$:

$$252=198\cdot1+54,\quad198=54\cdot3+36,\quad54=36\cdot1+18,\quad36=18\cdot2$$

이므로 $18$이다. 거꾸로 따라가면 $18=54-36=54-(198-3\cdot54)=4\cdot54-198=4(252-198)-198=4\cdot252-5\cdot198$이다.

확인 문제

$17x+5y=1$을 만족하는 정수 $x$, $y$를 하나 구하시오.

풀이 보기

$17=5\cdot3+2$, $5=2\cdot2+1$이다. 거꾸로 $1=5-2\cdot2=5-2(17-3\cdot5)=7\cdot5-2\cdot17$이므로 $x=-2$, $y=7$이다. (일반해: $x=-2+5t$, $y=7-17t$)

정리

  • $\gcd(a,b)=\gcd(b,\ a\bmod b)$
  • $\gcd(a,b)$는 $ax+by$ 꼴의 가장 작은 양수이다.
알림: 보호된 콘텐츠입니다.