유클리드호제법

유클리드 호제법과 디오판토스 방정식

일반적으로 두 자연수의 최대공약수를 구하기 위해 우리는 두 수를 소인수 분해한다. 예를 들어 두 자연수 $a$와 $b$가 있고 이들을 소인수 분해한 것이 $a=pq^2$이고 $b=p^2q$인 경우 두 수의 최대공약수 $g=pq$이다. 이때 $g=(a,b)=pq$로 쓸 수 있다. 이 방법은 분명 효과적이지만 두 수가 매우 큰 경우 그리 효과적인 방법은 아니다. 이 글에서는 두 수의 최대공약수를 구하는 다른 방법인 유클리드 호제법에 대해 다룬다. 유클리드 호제법 유클리드 호제법은 다음과 같은 정리이다. 두 자연수 $a$와 $b$가 있을 때 $a=bq+r$ ($q,r \in \mathbb{Z}$)라면 $(a,b)=(b,r)$이다. 이에 대한 증명은 다음과 같다. $(a,b)=G$라고 하고 $a=GA$, $b=..