유클리드 호제법
유클리드 호제법 정수 $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$의 공약수. 어떤 두 수의 공약수는 그 두 수의 최대공약수의 ..
2022. 9. 3.
