Number Theory - 2.4 유클리드 호제법

유클리드 호제법

$$ a=qb+r~~~\Longrightarrow ~~~ gcd(a,b)=gcd(b,r) $$

유클리드 호제법은 두 수의 최대공약수 뿐만 아니라 $ax+by=k \cdot gcd(a,b)$ 같은 선형 방정식을 풀어주기도 한다. 이를 확장 유클리드 호제법이라 부른다.

증명

$d=gcd(a,b)$면 $d ~\vert~ a,~ d ~\vert~ b$로 부터 $d ~\vert~ a - qb = r$ 를 얻는다.

따라서 $d$는 $b$와 $r$의 공약수이다.

임의의 $c$가 $b$와 $r$의 공약수이면 $c ~\vert~ qb+r=a$ 이다.

즉, $c$는 $a$와 $b$의 공약수이기도 하다.

$gcd(a,b)=d$ 이므로 $c \le d$ 이기 때문에 $d$ 는 $b$와 $r$의 공약수 중 가장 크다.

그러므로 $gcd(b,r)=d$ 이다. $\square$

과정

실제로 유클리드 호제법이 어떻게 진행되는지 보자.

두 정수 $a, b$의 $gcd(a,b)$ 를 찾기 위해 나눗셈 정리를 이용해 나열한다.

$$ \begin{aligned} a&=&q_1b+r_1~(0 < r_1 < b)\\ b&=&q_2r_1+r_2~(0 < r_2 < r_1)\\ r_1&=&q_3r_2+r_3~(0 < r_3 < r_2)\\ \vdots\\ r_{n-2}&=&q_nr_{n-1}+r_n~(0 < r_n < r_{n-1})\\ r_{n-1}&=&q_{n+1}r_n {\color{salmon} +0 } \end{aligned} $$

나머지가 $0$이면 최대공약수를 찾은 것이다.

$gcd(a,0)=a$ 이기 때문이다.

이 때의 최대공약수는 $r_n$ 이다.

---

이러한 과정은 유한한 연산끝에 종료된다.

$r_n=r_{n-2}-q_nr_{n-1}$ 과 같이 표현되고 이는 $r_{n-1}, r_{n-2} \cdots$도 마찬가지 일 것이다.

식을 거슬러 올라가면 $a, b$ 값들도 얻을 수 있고, 이것들이 $a, b$로 표현될 때 까지 반복하면

$$ ax+by=gcd(a,b) $$

의 해 $(x, y)$ 를 얻는다.

이를 실제 코드로 나타내는 것은 약간의 최적화를 필요로 한다. 실제로 다시 최대공약수를 찾은다음에 거슬러 올라가서 방정식의 해를 찾기보단, 해를 계속해서 업데이트하며 최대공약수를 찾을때의 해 값이 정답이 되게 한다.

확장 유클리드 호제법 알고리즘

6개의 변수를 유지하며 진행한다.

초기값은 다음과 같다.

• $r_1=a$
• $r_2=b$
• $x_1=1$
• $x_2=0$
• $y_1=0$
• $y_2=1$

그리고 $r_2 \ne 0$일 때 까지 다음을 반복한다.

$$ \begin{aligned} q \coloneqq \left\lfloor \dfrac {r_1}{r_2} \right\rfloor\\ (r_1,r_2) \coloneqq (r_2, r_1-qr_2)\\ (x_1,x_2) \coloneqq (x_2, x_1-qx_2)\\ (y_1,y_2) \coloneqq (y_2, y_1-qy_2) \end{aligned} $$

이것의 결과는 $r_2=0$ 일 때,

$r_1=gcd(a,b)$ 이고, $(x_1,y_1)$는 $ax+by=gcd(a,b)$ 를 만족하는 해이다.

코드로 나타내면 다음과 같다.

array<int, 3> gcdx(int a, int b) {  
   int x1 = 1, x2 = 0, y1 = 0, y2 = 1;  
   while (b) {  
      int q = a / b - ((a ^ b) < 0 && a % b);  
      tie(a, b) = mp(b, a - q * b);  
      tie(x1, x2) = mp(x2, x1 - q * x2);  
      tie(y1, y2) = mp(y2, y1 - q * y2);  
   }  
   return {a, x1, x2};  
}

$q$가 음수가 되면 c++ 의 연산상 내림 연산이 다르게 동작하기 때문에 따로 처리해준 것을 볼 수 있다.

유클리드 호제법으로부터 파생되는 정리들

Theorem 2.7

$$ k>0 \text{ 이면 } gcd(ka,kb)=k \cdot gcd(a,b) $$

증명

유클리드 호제법으로 $gcd(a,b)$ 를 찾는 과정을 전개하며 양변에 $k$를 곱해보자.

$$ \begin{aligned} ka=kq_1b+kr_1\\ kb=kq_2r_1+kr_2\\ kr_1=kq_3r_2+kr_3\\ \vdots\\ kr_{n-2}=kq_nr_{n-1}+kr_n\\ kr_{n-1}=kq_{n+1}r_n+0 \end{aligned} $$

이는 $gcd(ka,kb)$에 유클리드 호제법을 취하는 과정과 동일하고

이 때의 $gcd(ka,kb)=kr_n=k \cdot gcd(a,b)$ 이다. $\square$

$k$가 음수일 때도 비슷하게 $gcd(ka,kb)=\lvert~ k ~\rvert gcd(a,b)$ 인 따름 정리가 존재한다.

$gcd(n,m)=gcd(n,n-m)$

유클리드 호제법은 $gcd(n,m)=gcd(m,n \% m)$ 이다.

이것 말고도 $gcd(n,m)=gcd(n,n-m)$ 도 성립한다.

증명

$n=qm+r$ 일 때,

$d=gcd(n,m), e = gcd(m, r)$

$d ~\vert~ n,~ d ~\vert~ m$

$d ~\vert~ (n-qm)=r$

즉, $d ~\vert~ r,\, d ~\vert~ m$ 이기 때문에 $d ~\vert~ e. ~~ \because e=gcd(m,r)$

$e ~\vert~ m,\, e ~\vert~ r$ 이기 때문에 $e ~\vert~ (qm+r)=n$

$d ~\vert~ e$ 그리고 $e ~\vert~ d$ 이기 때문에 $d=e$ $\square$

최소공배수

Definition 2.4

$0$이 아닌 두 정수 $a,b$의 최소공배수 (least common multiple) 는 다음을 만족하는 양의 정수 $m$ 이며 $lcm(a,b)$로 표현된다.

1. $a ~\vert~ m, b ~\vert~ m$
2. $a ~\vert~ c,~b ~\vert~ c,~ c > 0$ 이면 $m \le c$

Theorem 2.8

$$ gcd(a,b) \cdot lcm(a,b)=a \cdot b $$

증명

$d=gcd(a,b),~ a=dq_1,~b=dq_2$ 라 하자.

$m=\dfrac {ab}d$이면 $m=da=db=dq_1q_2$

즉, $m$은 $a,b$의 공배수이다.

양의 정수 $c$를 $a,b$의 공배수 중 하나라고 하자.

$c=au=bv$

$d=ax+by$를 만족하는 $x,y$가 존재하므로

Theorem 2.4

$\dfrac cm=\dfrac {cd}{ab}=\dfrac {c(ax+by)}{ab}=\dfrac cb \cdot x+\dfrac ca \cdot y = vx+uy$

우변이 정수여서 $m ~\vert~ c$ 이므로 $m \le c$ 이고 $m$ 은 최소공배수이다.

$\therefore m=lcm(a,b)=\dfrac {ab}{gcd(a,b)} ~ \square$

Corollary

임의의 정수 $a, b$에 대해 $lcm(a,b)=ab$ 이면 $gcd(a,b)=1$ 이다. 역도 성립한다.