정수론 | 확장 유클리드 알고리즘, 선형 디오판토스 방정식

선형 디오판토스 방정식

간단히 말하면 부정방정식 중 정수해만을 구하는 방정식을 말한다. 디오판토스 방정식에는 여러 형태가 있지만 유클리드 호제법과 베주 항등식에 나오는 식과 유사한 ax+by=c를 선형 디오판토스 방정식(Linear Diophantine equation)이라 부른다. c=gcd(a,b)면 베주 항등식이 된다.

정리: $a,b \in N$이라고 하자. 그러면 $gcd(a,b)=ax+by$를 만족하는 정수 $x,y\in Z$가 존재한다.

베주 항등식의 해는 유일하지 않으며 확장된 유클리드 호제법으로 구할 수 있다.

해가 존재하는 지 증명

$S={ax+by\ |\ x,y\in Z}$라 정의하고 집합 S가 다음 세개의 성질을 만족함을 증명하자.

1. $a,b\ \in S$

   $a=a\cdot1+b\cdot0\in S,\ b=a\cdot0+b\cdot1 \in S$

2. $u \in S \implies u\cdot t \in S,\ \forall t\in Z$

   $u\in S$이면 $\exists\ x_1,y_1 \in Z\ s.t. u=ax_1+by_1$이며 $u \cdot t=t(ax_1+by_1)=a(tx_1)+b(ty_1)\in S$

3. $u_1,u_2 \in S \implies u_1\pm u_2 \in S$

   $u_1,u_2 \in S$라 하면 $u_1=ax_1+by_1$, $u_2=ax_2+by_2$를 만족하는 정수 $x_1,x_2,y_1,y_2$가 존재한다.

   $u_1\pm u_2=ax_1+by_1 \pm\ (ax_2+by_2) = a(x_1\pm x_2)+b(y_1\pm y_2) \in S$

따라서 $a=bq+r,\ 0\le r<b$에 대하여 $a,b \in S$이므로 $a-bq=r\in S$이다. $r=0$인 경우 gcd(a,b)=b이고 $r\ne0$이면 $b=rq_1+r_1,\ 0\le r_1<r$로 표현할 수 있고 $b,r\in S$이므로 $r_1=b-rq_1$이 되어 S의 원소가 된다. 이를 마지막까지 반복하면 $r_n=gcd(a,b)\in S$가 되어 gcd(a,b)=ax+by를 만족하는 정수 x, y가 존재하며 유클리드 알고리즘의 증명도 할 수 있다.

선형 디오판토스 방정식의 일반해

그렇다면 베주 항등식이 아니라 선형 디오판토스 방정식 $ax+by=c$에 대해 (x,y)의 해를 구해보자. 이전 포스팅과 위에서 베주 항등식 $ax+by=gcd(a,b)=d$에 대해 성립하게 만드는 x, y가 반드시 존재하고 $ax+by$로 표현되는 모든 정수는 d의 배수임을 확인하였다.

즉, 앞서 베주 항등식을 토대로 $ax+by=c$의 해가 존재 유무와 c는 $gcd(a,b)$의 배수라는 조건은 서로 필요충분조건임을 확인하였다. 선형 디오판토스 방정식의 특수해가 존재하고 우변이 a와 b의 최대공약수의 배수임을 알아냈으니 일반해를 표현해보자.

(x,y)가 임의의 해라고 가정하면 $ax_0+by_0=ax+by$이고 이를 정리하면 $a(x-x_0)=-b(y-y_0)$이다. 여기서 양변을 $gcd(a,b)=d$로 나누면 $\cfrac{a}{d}(x-x_0)=-\cfrac{b}{d}(y-y_0)$인데 $gcd(\cfrac{a}{d},\cfrac{b}{d})=1$이므로 $\cfrac{a}{d}|y-y_0$이다. 따라서 적당한 정수 $k_x$에 대해 정리하면 $\cfrac{a}{d}k_x=-(y-y_0)$이고 정리하면 $y=y_0-\cfrac{a}{d}k_x$이다. 마찬가지로 x에 대해 정리하면 $x=x_0+\cfrac{b}{d}k_y$를 얻는다. 따라서 $d=gcd(a,b)$이므로 ax+by=c의 정수해 (x,y)는 특수해 $x_0,y_0$에 대해 $[(x_0+\cfrac{b}{d}k,y_0-\cfrac{a}{d}k),k\in Z]$로 표현할 수 있다.

확장 유클리드 호제법

확장 유클리드 호제법은 유클리드 호제법을 역으로 계산하여 $ax+by=c$를 만족하는 (x,y)쌍을 구하는 알고리즘이다.

먼저 x,y의 점화식을 도출하기 위해 이전의 유클리드 호제법 과정을 다시 작성해보자.

$a=bq+r_2$

$b=r_2q_2+r_3$

$r_2=r_3q_3+r_4$

$\cdots$

$r_n=r_{n+1}q_{n+2}$와 같이 전개가 되어 결국 마지막에 남는 값이 최대공약수가 되고 이것을 참고하면 아래와 같은 조건이 생긴다.

$r_{n+2}=r_n-r_{n+1}q_{n+2},\ ax_n+by_n=r_n$

$=ax_n+by_n-(ax_{n+1}+by_{n+1})q_{n+2}$

$=a(x_n-x_{n+1}q_{n+2})+b(y_n-y_{n+1}q_{n+2})$

$\implies (x_{n+2},y_{n+2})=(x_n-x_{n+1}q_{n+2},y_n-y_{n+1}q_{n+2})$

위와 같이 점화식을 도출하였고 유클리드 호제법의 결과에 따라 $gcd(a,b)=r_{n+2}$라 하자. 그리고 점화식의 초항이 필요한데 유클리드 호제법의 전개식을 보면 a와 b에 대해서도 r과 같이 해석할 수 있으므로 $r_0=a,\ r_1=b$라 하면 $a=ax_0+by_0$에서 $(x_0,y_0)=(1,0)$이고 $b=ax_1+by_1$에서 $(x_1,y_1)=(0,1)$이다. x, y에 대해 점화식과 초항을 구하였으므로 차례대로 계산하면 된다. 아래 예시를 구해보자.

예제

두 수 710, 68의 최대공약수를 구하고 $gcd(710,68)=710x+68y$를 만족하는 정수 x, y를 구하여라.

유클리드 호제법을 사용하면 gcd(710,68)은 금방 아래와 같이 구할 수 있다.

$710=68\cdot10+30$

$68=30\cdot2+8$

$30=8\cdot3+6$

$8=6\cdot1+2$

$6=2\cdot3$으로 $gcd(710,68)=2$를 구하였다.

이제 이걸 다시 역산하면 x, y값이 아래와 같이 나온다.

$2=8-6 \qquad \Longleftarrow 2=8-6$

$=4\cdot8-30 \quad \Longleftarrow 6=30-8\cdot3$

$=68\cdot4-30\cdot9 \quad \Longleftarrow 8=68-30\cdot2$

$=710\cdot(-9)+68\cdot94 \quad \Longleftarrow 30=710-68\cdot10$

$\therefore x=-9,\ y=94$

정수해가 구해졌으므로 위의 베주항등식의 일반해에 대입하면 다른 해를 구할 수 있다. 위에서 구한 일반해에 대입하면 (x,y)는 각각 $(-9+\cfrac{68}{2}k,94-\cfrac{710}{2}k)$로 k가 어떤 정수건 다른 해를 만들 수 있다. 예를 들어 1을 대입 시 (25,-261)이 나오는데 문제에 제시된 수식에 대입하면 $710\cdot25+68\cdot(-261)=2$가 성립한다.

정리: $a,b\in N$에 대하여, $gcd(a,b)=1$과 $\exists x,y\in Z\quad s.t.\ ax+by=1$은 필요충분관계이다.

앞서 베주 항등식을 통해 증명하였으므로 생략하겠다.

정리: $ax+by=1$이면 $gcd(a,b)=gcd(a,y)=gcd(x,b)=gcd(x,y)=1$이 성립한다.

정수해를 갖는 조건이라면 베주 항등식에 따라 우변은 gcd(a,b)의 배수여야 하므로 gcd(a,b)=1이다. 그리고 a, b와 똑같은 관점으로 다른 미지수에도 적용 가능하므로 제시된 조건을 만족한다.

정리: $a,b\in N$에 대해 $gcd(a,b)=d\Rightarrow gcd(\cfrac{a}{d},\cfrac{b}{d})=1$

정리: $a,m,n\in N$라 하면, $gcd(a,mn)=1 \iff gcd(a,m)=1$이고 $gcd(a,n)=1$이다.

필요충분조건임을 증명하기 위해 제시된 명제와 그 역이 성립함을 증명하자.

$gcd(a,mn)=1$일 때 $ax+mny=1$을 만족하는 정수 x, y가 존재한다. $a(x)+m(ny)=1$로 보면 $gcd(a,m)=1$이며 $a(x)+n(my)=1$로 보면 $gcd(a,n)=1$이다.

역으로 $gcd(a,m)=gcd(a,n)=1$이라 하자. 그럼 $ax_0+my_0=1$과 $ax_1+ny_1=1$을 만족시키는 정수 $x_0,x_1,y_0,y_1$이 존재한다.

$1=ax_0+my_0(ax_1+ny_1)=ax_0+amx_1y_0+mny_0y_1$

$=a(x_0+mx_1y_0)+mn(y_0y_1)=1$

$\therefore gcd(a,mn)=1$

정리: $a,b,S\in N$이라 하자. $a|S$, $b|S$, $gcd(a,b)=1$이면 $ab|S$이다.

$a|S,\ b|S$에 따라 적당한 정수 x, y에 대해 $ax=by=S$이다. 그렇다면 $a|by$가 성립하고 gcd(a,b)=1에 따라 $a|y$이다. 그리고 적당한 정수 z가 존재하여 $az=y$이고 $S=b\cdot az=abz$가 되어 $ab|S$를 만족한다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저