Number Theory - 2.4 유클리드 호제법
유클리드 호제법
유클리드 호제법은 두 수의 최대공약수 뿐만 아니라 $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)$ 를 찾기 위해 나눗셈 정리를 이용해 나열한다.
나머지가 $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$로 표현될 때 까지 반복하면
의 해 $(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$일 때 까지 다음을 반복한다.
이것의 결과는 $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
증명
유클리드 호제법으로 $gcd(a,b)$ 를 찾는 과정을 전개하며 양변에 $k$를 곱해보자.
이는 $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)$로 표현된다.
- $a ~\vert~ m, b ~\vert~ m$
- $a ~\vert~ c,~b ~\vert~ c,~ c > 0$ 이면 $m \le c$
Theorem 2.8
증명
$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$ 이다. 역도 성립한다.
Comments