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

April 17, 2023

디오판투스 방정식Permalink

디오판투스 방정식 (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$ 이다.

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

선형 디오판투스 방정식 $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$