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

일반적으로 두 자연수의 최대공약수를 구하기 위해 우리는 두 수를 소인수 분해한다.

예를 들어 두 자연수 $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=GB$라고 하자. (그럼 $(A,B)=1$이다.)
$a=bq+r$에서 $bq$를 이항 하면 $a-bq=r$이다. $a,b$를 대입하면 $GA-GBq=r$, $G(A-Bq)=r$이다. 즉, $r$이 $G$를 인수로 가지는 것은 확인했다. 이제 $(B, A-Bq)=1$만 확인하면 $(b,r)=G$이다.
만일 $(B, A-Bq) = m \neq 1$이라면 $B=mk$, $A-Bq=ml$이다. (이때 $(k,l)=1$).
한편 $A=(A-Bq)+Bq=ml+mkq$이다. 따라서 $(A,B)=(m(l+kq), mk)=m \neq 1$이므로 $A$와 $B$가 서로소라는 조건과 모순되므로 $m=1$일 수 밖에 없다. 따라서 $(B,A-Bq)=1$이다.
따라서 $(a,b)=(b,q)=G$이다.

이를 활용하여 123456789와 12345678의 최대공약수를 구해보면 다음과 같다.

$123456789=12345678 \times 10 +9$, $(123456789,12345678)=(12345678,9)$

12345678에 9의 배수판정법을 사용하면 $1+2+3+4+5+6+7+8=9 \times 4$이므로 9의 배수이다. 따라서 12345678과 9의 최대공약수는 9이고, 123456789과 12345678의 최대공약수도 9이다.

---

유클리드 호제법 활용

유클리드 호제법을 이용하면 복잡한 디오판토스 방정식의 해를 쉽게 구할 수 있다. 다음 $x$, $y$에 관한 방정식의 정수근을 생각해보자.

$541x+142y=400$

다음은 541과 142에 대해 유클리드 호제법을 사용한 것이다.

$\begin{vmatrix}541&142\\426&\\115&142\\&115\\115&27\\108&\\7&27\\&21\\7&6\\6&\\1&6\\&6\\1&0\end{vmatrix}$

그리고 다음은 유클리드 호제법으로부터 식을 몇 개 적고, 그를 변형한 것이다.

$541=142 \times 3+115$	$115=541+142 \times (-3)$
$142=115 \times 1+27$	$27=142+115\times (-1)$
$115=27 \times 4+7$	$7=115+27\times (-4)$
$27=7 \times 3+6$	$6=27+7\times (-3)$
$7=6 \times 1+1$	$1=7+6\times (-1)$

우선은 위 식을 가지고 $541x+142y=1$의 정수해부터 구해보자. 다음과 같이 식에 다른 식을 대입, 변형, 대입 변형을 반복하여 원하는 형태가 나올 때까지 반복한다.

$1=7+6\times (-1)$에 $6=27+7\times (-3)$ 대입 → $1=7+(27+7\times (-3))(-1)$, $1=(-1)27+(4)7$

$1=(-1)27+(4)7$에 $7=115+27\times (-4)$ 대입 → $1=(-1)27+4(115+27(-4))$, $1=(-17)27+(4)115$

$1=(-17)27+(4)115$에 $27=142+115(-1)$ 대입 → $1=4(115)+(-17)(142+115(-1))$, $1=(21)115+(-17)142$

$1=(21)115+(-17)142$에 $115=541+142(-3)$ 대입 → $1=21(541+142(-3))+(-17)(142)$, $1=(21)541+(-80)142$

$541(21)+142(-80)=1$

따라서 $541x+142y=1$의 정수해의 예시는 $(x,y)=(21,-80)$이다.

그리고 이 식의 좌우 변에 정수 $k$를 곱하면 $541xk+142yk=k$이며, 이 방정식의 정수근의 예는 $(x,y)=(21k,-80k)$이다.

이 정수근의 예시로부터 다른 근들을 구할 수 있다. 142와 541는 서로소이니 정수 $m$를 이용해서 서로 일정양을 빼거나 더해주는 식으로 $x$와 $y$를 구성하면 $(x,y)=(21k+142m,-80k-541m)$이다.

$m$의 값이 증가하면 $541x$의 크기가 커지는 만큼 $142y$의 값이 작아지는 방식으로 $=k$를 만족하는 것이다.

위의 논의를 바탕으로 $541x+142y=400$의 정수해를 모두 구해보자.

$k=400$이 되므로 한 정수해의 예는 $(x,y)=(8400,-32000)$이다. 여기에 정수 $n$을 이용하여 다른 해를 유도하면 $(x,y)=(8400+142m,-32000-541m)$, $m \in \mathbb{Z}$이다.

이러한 방법으로 $a$, $b$, $c$가 모두 정수인 $x$, $y$에 관한 방정식 $ax+by=c$의 정수해를 전부 구할 수 있다.