정수론, 그 열 번째 이야기 | 디오판토스 방정식

 

디오판토스 방정식이란 하나 이상의 미지수를 갖는 임의의 방정식의 정수해를 구하는 문제를 말한다.

우리가 생각하는 가장 간단한 형태는 이변수 선형 디오판토스 방정식이다. 이는 $$ax + by = c$$ 와 같은 꼴을 갖는데, 여기서 $a, b, c$ 는 모두 정수이고 $a, b$ 는 적어도 하나는 $0$ 이 아니다.

 

그리고 $ax + by = c$ 꼴의 방정식의 해에 대해 다음과 같은 정리가 알려져 있다.

 

$ax + by = c$ 가 해를 가지는 것은 $d = gcd\left( a, b \right )$ 일 때, $d \mid c$ 임과 동치이다.      $x_0, y_0$ 가 이 방정식의 특이해라면, 다른 모든 해들은 임의의 정수 $t$ 에 대해 다음과 같이 표현된다.$$x = x_0 + \left ( \frac{b}{d} \right ) t$$ $$y = y_0 - \left ( \frac{a}{d} \right ) t$$

 

Proof :

해의 존재성을 먼저 보이자.

 

만약 $ax + by = c$ 의 해가 존재하는 경우 $x_0, y_0 \in \mathbb{Z}$ 에 대해 $ax_0 + by_0 = c$ 이고

$d = gcd \left ( a, b \right )$ 라고 하면, $\exists r, s \in \mathbb{Z}\;s.t.\;a = dr, b = ds$

따라서 $c = ax_0 + by_0 = drx_0 + dsy_0 = d \left (rx_0 + sy_0 \right )$ 이고, $d \mid c$ 이다.

 

만약 $d \mid c$ 이면, $\exists t \in \mathbb{Z}\;s.t.\;c = dt$ 이고,

또한 $d = ax_0 + by_0$ 인 정수 $x_0, y_0$ 가 존재하므로 $$c = dt = d \left ( ax_0 + by_0 \right ) = a\left (tx_0\right ) + b \left ( ty_0 \right )$$ 이므로, $ax + by = c$ 는 특이해 $x = tx_0, y = ty_0$ 를 갖는다.

 

해의 존재성을 보였으므로, 일반해의 형태를 보자.

$ax + by = c$ 의 특이해 $x_0, y_0$ 에 대해, 다른 해를 $x', y'$ 이라고 하면 $$ax_0 + by_0 = c = ax' + by'$$ 이고, 이는 $a \left (x' - x_0 \right ) = b \left (y_0 - y'\right )$ 를 의미한다.

 

또한, 서로소인 정수 $r, s$ 가 존재하여 $a = dr, b = ds$ 를 만족하므로 이를 위의 식에 대입하면 $$r\left(x'-x_0\right) = s\left(y_0-y'\right)$$ 인데 $r \mid s\left(y_0 - y'\right)$ 이고 $gcd \left (r, s\right) = 1$ 이므로 $ r\mid \left (y_0 - y'\right) $ 이다.

 

다시 말해, 어떤 정수 $t$에 대해 $y_0 - y' = rt$ 이다.

이를 통해 $x'-x_0 = st$ 를 얻고, 이로부터 다음과 같은 식을 유도할 수 있다.

$$x' = x_0 + st = x_0 + \left( \frac{b}{d} \right ) t$$ $$y' = y_0 - rt = y_0 - \left ( \frac{a}{d} \right ) t$$

 

또한, 이를 원래 방정식에 대입하는 것을 통해 디오판투스 방정식을 만족함을 알 수 있다.

 

따라서 정수 $t$ 를 선택함에 따라 무한히 많은 해를 구할 수 있음을 알 수 있다.