The Linear Diophantine Equation
Definition 1. Let $a, b, c \in \mathbb{Z}$ with $a \neq 0, b \neq 0$. The equation $$ax + by = c$$ that is to be solved in the integers is called the linear diophatine equation in two unknowns.
교과과정에서는 일차 부정방정식으로 소개되는 선형 디오판토스 방정식이다. 보통 정수를 계수로 가지는 다항식의 정수해를 찾는 것을 의미한다. 해를 가지는 조건과 해의 구체적인 형태가 깔끔하게 알려져 있다.
Theorem 1
Theorem 1. The linear diophantine equation $ax + by = c$ has a solution $\iff$ $d \,|\, c$, where $d = \gcd(a, b)$. If $x_0, y_0$ is any particular solution of this equation, then all other solutions are given by $$x = x_0 + (\frac{b}{d})t \\ y = y_0 - (\frac{a}{d})t,$$ where $t \in \mathbb{Z}$.
Proof. Denote $(x_0, y_0)$ to be a solution of the equation. Then $d \,|\, ax_0 + y_0 = c$. Conversely, suppose that $c = md$ for some $m \in \mathbb{Z}$. By Theorem 3, $d = ax_0 + by_0$ for some $x_0, y_0 \in \mathbb{Z}$. Then $c = md = m(ax_0 + by_0) = a(mx_0) + b(my_0)$. Thus the equation has a solution.
If $x', y'$ are any other solution, then $$ax_0 + by_0 = c = ax' + by' \\ \Longrightarrow a(x' - x_0) = b(y_0 - y').$$ Since $\gcd(a, b) = d$, $a = rd, b = sd$ for some $r, s \in \mathbb{Z}$. Then $$a(x' - x_0) = b(y_0 - y') \Longrightarrow r(x' - x_0) = s(y_0 - y').$$ Note that $r \,|\, s(y_0 - y')$ and $s \,|\, r(x' - x_0)$. Since $\gcd(r, s) = 1$, $r \,|\, y_0 - y'$ and $s \,|\, x' - x_0$ by Euclid Lemma. Then $y_0 - y' = rt$ for some $t \in \mathbb{Z}$. Thus $$r(x' - x_0) = s(y_0 - y') \Longrightarrow x' - x_0 = st \\ \Longrightarrow x' = x_0 + st = x_0 + (\frac{b}{d})t.$$ Similarly, $$r(x' - x_0) = s(y_0 - y') \Longrightarrow rt = y_0 - y' \\ \Longrightarrow y' = y_0 - rt = y_0 - (\frac{a}{d})t.$$
For any integer $t$, $$ax' + by' = a(x_0 + (\frac{b}{d})t) + b(y_0 - (\frac{a}{d})t) \\ = ax_0 + by_0 + (\frac{ab}{d} - \frac{ab}{d})t = c + 0 = c.$$ $\blacksquare$
만일 자연수 해 만을 찾고 싶다면 조건 $x' > 0, y' > 0$으로부터 $t$에 관한 부등식을 잡아내서 해당하는 값 만을 택하면 된다.
