Number Theory - 2.5 디오판투스 방정식

디오판투스 방정식

디오판투스 방정식 (Diophantine equation)은 하나 이상의 미지수를 갖는 임의의 방정식의 정수해를 구하는 문제이다.

간단한 형태의 디오판투스 방정식, 그리고 이 단원에서 보통 다루게 될 꼴은 두 개의 미지수를 갖는 선형 디오판투스 방정식이다.

$$ ax+by=c $$

단, $a,b,c \in \Z,~~a$와 $b$는 적어도 하나가 $0$이 아님

위 디오판투스 방정식의 해가 존재할 필요충분조건은 $gcd(a,b) \mid c$ 여야 한다.

증명은 다음과 같다.

$d=gcd(a,b),~~a=dr,b=ds$, (단, $gcd(r,s)=1$) 라고 하자.

$c=ax+by=drx+dsy=d(rx+sy)$ 이므로 $d \mid c$

역으로, $d \mid c$라면 $d=ax+by$의 양변에 $c/d$를 곱하면 $c=\dfrac {axc}d+\dfrac {byc}d$

$c=a(xc/d)+b(yc/d)$ 처럼 $ax+by=c$ 꼴로 나타낼 수 있다. $\square$

해를 찾는 법

$ax+by=c$ 의 해 $(x,y)$를 찾는데 집중해보자.

일단 $ax+by=c$의 해를 찾기 전에 $ax+by=gcd(a,b)$의 해를 찾는 것은 확장 유클리드 호제법을 이용해 찾을 수 있다.

$d=gcd(a,b)$ 그리고 $ax+by=c$를 만족하는 특이해 $x_0,y_0$은 다음과 같이 찾는다.

단, $d \mid c$이다.

$ax+by=d$를 만족하는 $x, y$를 $x_{gcd},y_{gcd}$ 라고 할 때,

$$ \begin{aligned} ax_{gcd}+by_{gcd}=d\\ ax_{gcd}\cdot \dfrac cd+by_{gcd}\cdot \dfrac cd=c \end{aligned} $$

즉 일반해 $x_0=x_{gcd} \cdot c/d$ 이고, $y_0=y_{gcd} \cdot c/d$ 이다.

이제 일반해의 식을 찾아보자.

Theorem 2.9

선형 디오판투스 방정식 $ax+by=c$ 가 해를 가지는 것은 $gcd(a,b) \mid c$와 동치이다.

$x_0,y_0$ 가 이 방정식의 특이해라면, 다른 모든 해들은 $t$가 정수일 때

$$ x=x_0+t(b/d),~y=y_0-t(a/d) $$

로 나타낼 수 있고 무수히 많은 해가 존재한다.

증명

이미 $gcd(a,b) \mid c$ 일 때의 특이해가 존재한다는 것을 보였으므로, 이 때의 특이해를 $(x_0, y_0)$ 이라 하고, 다른 해를 $(x', y')$ 이라 하자.

$$ c=ax_0+by_0=ax'+by'\\a(x'-x_0)=b(y_0-y') $$

$d=gcd(a,b)$ 라고 할 때, $a=dr, b=ds$ 로 두고, $(gcd(r,s)=1)$

$$ \begin{aligned} dr(x'-x_0)=ds(y_0-y')\\ r(x'-x_0)=s(y_0-y') \end{aligned} $$

여기서 $gcd(r,s)=1$ 이므로 유클리드 보조정리를 이용하면 $r \mid (y_0-y')$ 이다.

$y_0-y'=rt$ 라 두면, $x'-x_0=st$ 가 된다.

$$ \begin{aligned} \because r(x'-x_0)=s \cdot rt\\ x'-x_0=st \end{aligned} $$

정리해보면

$$ \begin{aligned} x'&=x_0+st=x_0+(b/d)t \\ y'&=y_0-rt=y_0-(a/d)t\\ \\ ax'+by'&=a[x_0+(b/d)t]+b[y_0-(a/d)t]\\ &=ax_0+by_0+(ab/d-ab/d)t=c \end{aligned} $$

처럼 항등식도 나오므로 무수히 많은 해 $x', y'$ 가 존재한다. $\square$