## Characterize the solutions of a linear Diophantine equation over QQ[x]

Suppose $f(x)$ and $g(x)$ are nonzero polynomials in $\mathbb{Q}[x]$ with greatest common divisor $d(x)$.

1. Given $h(x) \in \mathbb{Q}[x]$, show that there exist $a(x), b(x) \in \mathbb{Q}[x]$ such that $h = af + bg$ if and only if $h$ is divisible by $d$.
2. Given $h$, if $a_0$ and $b_0$ are a particular solution to the equation $a_0f + b_0g = h$, prove that every solution is of the form $a = a_0 + m\frac{g}{d}$ and $b = b_0 - m \frac{f}{d}$ for some $m \in \mathbb{Q}[x]$.

We will approach this problem from a more abstract point of view.

Lemma: Let $R$ be a Bezout domain and let $a,b \in R$ be nonzero. Suppose $(a,b) = (d)$ and $a = dt$. If $bc \in (a)$, then $c \in (t)$. Proof: Write $b = du$. Since $(a,b) = (d)$, we have $ax + by = d$ for some $x,y \in R$. Since $bc \in (a)$, we have $bc = ak$ for some $k$. Now $bcx = akx$, so that $bcx = k(d-by)$, and thus $b(cx + yk) = kd$. Then $u(cx + yk) = k$. Now $dtu(cx + yk) = au(cx + yk) = ak = bc = duc$, so that $t(cx + yk) = c$, and we have $c \in (t)$. $\square$

This lemma generalizes part (a) of this previous exercise.

Lemma: Let $R$ be a Bezout domain and let $a,b,h \in R$ with $(a,b) = (d)$. There exist $x,y \in R$ such that $ax + by = h$ if and only if $d|h$. Proof: If $d|h$, then $h \in (d) = (a,b)$, so that $x$ and $y$ exist with $h = ax + by$. Conversely, if $x$ and $y$ exist with $ax + by = h$, then $h \in (a,b) = (d)$, so that $d|h$. $\square$

Part (a) of this problem follows because $\mathbb{Q}[x]$ is a Euclidean domain, hence a principal ideal domain, and thus a Bezout domain.

Lemma: Let $R$ be a Bezout domain and let $a,b,x_0,y_0,h \in R$ such that $a,b \neq 0$, $(a,b) = (d)$, $d|h$, and $ax_0 + by_0 = h$. If $x,y \in R$ such that $ax + by = h$, then $x = x_0 + m\frac{b}{d}$ and $y = y_0 - m\frac{a}{d}$ for some $m \in R$. Proof: Note that $(ax + by) - (ax_0 + by_0) = h - h = 0$. Then $a(x - x_0) + b(y - y_0) = 0$, and thus $a(x - x_0) = b(y_0 - y)$. Now $a(x - x_0)$ is in $(b)$, so that by the first lemma, $x - x_0 \in (\frac{b}{d})$. Say $m\frac{b}{d} = x - x_0$; then $x = x_0 + m\frac{b}{d}$. Plugging this back into $a(x - x_0) = b(y_0 - y)$ and solving for $y$ (using the fact that $d$ divides $a$), we see that $y = y_0 - m\frac{a}{d}$. $\square$

Again, this solves the stated problem because $\mathbb{Q}[x]$ is a Bezout domain. But more generally, this lemma allows us to solve linear Diophantine equations in two variables over any Bezout domain.