유클리드 호제법

유클리드 호제법

정수 $a$, $b$, $n$에 대하여 $$(a,b)=(a,b+an)$$이다.

참고로, 유클리드 호제법을 자연수 $a$를 $b$로 나눈 몫을 $q$, 나머지를 $r$라고 할 때 $(a,b)=(b,r)$로 알고 있는 사람들도 많은데, 꼭 몫이나 나머지일 필요도 없고 자연수일 필요도 없습니다.

 

증명을 위해서 다음 보조정리를 사용합시다.

 

보조정리

자연수 $p$와 $q$ 에 대하여 $p \mid q$ 이고 $q \mid p$ 이면 $p=q$이다.

 

증명

최대공약수 $(a,b)=p$, $(a,b+an)=q$라 하자.

먼저 $p \mid a$, $p \mid b$이므로 $p \mid b+an$을 얻는다. 따라서 $p$는 $a$와 $b+an$의 공약수. 어떤 두 수의 공약수는 그 두 수의 최대공약수의 약수이므로 $p \mid q$이다.

다음으로 $q \mid a$, $q \mid b+an$이므로 $p \mid b+an$을 얻는다. 따라서 $q$는 $a$와 $b$의 공약수. 어떤 두 수의 공약수는 그 두 수의 최대공약수의 약수이므로 $q \mid p$이다.

$p \mid q$이고 $q \mid b$이므로 $p=q$을 얻는다.   $\blacksquare$

 

Exponential 17 김지하