유클리드 호제법 알아보기

유클리드 호제법이란?

양의 정수 $a, b$와 $a=bq+r$ 인 정수 $q, r$에 대해 $gcd(a, b) = gcd(b,r)$ 이다.

(이때 $gcd(a,b)$는 $a, b$의 최대공약수이다.)

 

증명하기

유클리드 호제법 증명

 

유클리드 호제법을 이용해 두 양의 정수의 최대공약수 구하기

두 양의 정수 $a, b$에 대하여 $a$를 $b$로 나누면 $a=bq_1+r_1$, ($0 \leq r_1 < a$)를 만족시키는 정수 $q_1, r_1$이 존재한다.

 

(1) $r_1 = 0$이라 하고 $b$를 $r_1$으로 나누면 $b=gcd(b,r_1) = gcd(a,b)$ 이다.

 

(2) $r_1 \neq 0$이라 하고 $b$를 $r_1$으로 나누면 $b=q_2r_1 + r2$, ($0 \leq r_2 < r_1$)을 만족시키는 정수 $q_2, r_2$가 존재한다.

 

만약, $r_2 =0$ 이면 $r_1 = gcd(r_1, r_2) = gcd(b, r_1) = gcd(a,b)$ 이다.

 

$r_2 \neq 0$ 이면 $r_1$을 $r_2$로 나눈다. 이와같은 과정을 계속 반복하면

$a>r_1 > r_2 > \cdots \leq 0$이므로 유한번 실행하면

$r_{n-2} = q_n r_{n-1}+r_n$ ($0<r_n<r_{n-1}, r_{n-1} = q_{n+1}r_n$) 이다.

 

유클리드 호제법에 의해 $r_n = gcd(r_{n-1},r_n) = \cdots = gcd(r_1,r_2) = gcd(b,r_1) = gcd(a,b)$ 를 만족한다.