유클리드 호제법, 유클리드 알고리즘(Euclid algorithms)

유클리드 호제법은 지금 고교 교육과정에 포함되어 있지 않지만 알고 있을 때 복잡한 문제를 해결하는데 약간의 도움이 되는 경우도 있습니다. 유클리드 호제법은 고대 그리스 수학자 유클리드(Euclid)가 만든 것이며, 그의 책에서 두 정수의 최대공약수를 찾는 알고리즘 중 하나입니다. 최대공약수를 찾을 때 두 수의 크기가 매우 커지게 되는 경우에는 더 이상 직관적으로 또는 암산으로 최대공약수를 찾기가 어려워지기 때문에, 나눗셈 알고리즘을 통해 수를 충분히 줄이면서 유클리드 호제법을 사용하면 답을 구할 수 있게 됩니다.

---

1. 유클리드 호제법과 보조정리

 

유클리드 호제법을 증명하기 위해 유클리드 보조정리를 보이고 가는 것이 좋습니다. 사실 내용은 별 거 없고 지극히 당연한 내용입니다.

 

보조정리($N.T$) 1.1) 유클리드 보조정리
$a\mid (bc)$ 이고 $\gcd (a,b)=1$ 이면, $a\mid c$ 이다.

증명) 베주 항등식에 의하여, 주어진 정수 $a,b$ 에 대해 $ma+nb=g=\gcd (a,b)=1$ 을 만족하는 어떤 $m,n\in\mathbb{Z}$ 가 존재한다. 양변에 임의의 정수 $c$ 를 곱하면,

$$cma+cnb=c=m(ca)+n(cb)\;\;\;\;\cdots \;\;\;(1)$$
이 된다. 이제 $a\mid (bc)$ 가 주어졌다고 하자. 그러면 어떤 정수 $k$ 가 존재하여 $ak=bc$ 가 만족된다는 뜻이다. 이를 $(1)$ 에 대입하면,

$$m(ac)+n(bc)=m(ac)+n(ak)=a(mc+nk)=c$$
이다. 그런데 여기서 $mc+nk\in\mathbb{Z}$ 이므로, 이는 곧 $a\mid c$ 임을 의미한다. $_\blacksquare$

 

 

이제 유클리드 호제법을 증명합시다. 유클리드 호제법은 결국 나눗셈 알고리즘에 의하여 $a=bq+r\;\;(0\geq r < b)$ 의 관계에서, 피젯수 $a$ 와 젯수 $b$ 의 최대공약수는 젯수 $b$ 와 나머지 $r$ 의 최대공약수와 동일하다는 것입니다.

 

 

정리($N.T$) 1.9) 유클리드 호제법
주어진 두 정수 $a,b$ 에 대하여 $a=bq+r\;\;(0\geq r < b)$ 가 성립할 때, 다음이 성립한다.
$$g=\gcd (a,b)=\gcd (b,r)$$

증명) $g_1=\gcd (a,b)$ 이고 $g_2=\gcd (b,r)$ 이라 하자. $g_1=g_2$ 임을 보여야 한다. 이 '같음'을 보이기 위해 양쪽 부등호가 성립한다는 논리를 사용할 것이다.

$g_1\mid a$, $g_1\mid b$ 이므로 $a=mg_1$, $b=ng_1$ 이 되는 $m,n\in\mathbb{Z}$ 가 성립한다. 그러면 $a=bq+r\;\;(0\geq r < b)$ 의 관계에서

$$mg_1=ng_1\cdot q +r \;\;\Rightarrow \;\; r=(m-nq)\cdot g_1 \;\; \Rightarrow \;\; g_1\mid r$$
이다. 그러면 $g_1$ 은 $b$ 와 $r$ 을 모두 나누기 때문에 $b,r$ 의 공약수이다. 이때 정의($N.T$) 1-5) 의 ③ 에 의하면 $c\mid x$ 이고 $c\mid y$ 인 어떤 정수 $c$ 가 존재할 때, $\gcd (x,y)=g$ 라고 하면 반드시 $c\leq g$ 가 성립한다. 고로

$$g_2=\gcd (b,r) \geq g_1$$
가 성립한다. ($b,r$ 의 최대공약수 $g_2$ 는 그냥 공약수 $g_1$ 보다 반드시 같거나 커야 한다는 논리)

마찬가지로, $g_2\mid b$, $g_2\mid r$  이므로 $b=m'g_2$, $r=n'g_2$ 인 $m',n'\in\mathbb{Z}$ 가 존재한다. 그러면 $a=bq+r\;\;(0\geq r < b)$ 에서 

$$a=m'q\cdot g_2+n'g_2=(m'q+n)g_2 \;\; \Rightarrow \;\; g_2\mid a$$
를 얻는다. $g_2$ 는 $a,b$ 를 모두 나누므로 둘의 공약수이다. 다시 정의($N.T$) 1-5) 의 ③ 에 의하면 

$$g_1=\gcd (a,b)\geq g_2$$
가 성립한다. ($a,b$ 의 최대공약수 $g_1$ 은 그냥 공약수 $g_2$ 보다 반드시 같거나 커야 한다는 논리) 결과적으로 $g_1=g_2$ 를 얻는다. $_\blacksquare$

 

 

 

유클리드 호제법은 예시를 보는 것이 좋습니다. 과정을 잘 살려 보이기 위해서 사진으로 대체합니다.

---

예제 1) $\gcd (666,31)$ 의 값을 구하여라.

 

 

---

예제 2) $\gcd (5291,3108)$ 의 값을 구하여라.

 

 

 

 

 

[참고문헌]

Introduction to Number Theory - William W. Adams, Larry Joel Goldstein