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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: