# Solution of Diophantine equation for polynomials

I'm trying to solve this polynomial Diophantine equation for $R$ and $S$:

$AR + BS = G$

where

$A(x) = a_0x^{n_a} + a_1x^{n_a-1} + a_2x^{n_a-2} + ... + a_{n_a}$
$B(x) = b_0x^{n_b} + b_1x^{n_b-1} + b_2x^{n_b-2} + ... + b_{n_b}$
$R(x) = r_0x^{n_r} + r_1x^{n_r-1} + r_2x^{n_r-2} + ... + r_{n_r}$
$S(x) = s_0x^{n_s} + s_1x^{n_s-1} + s_2x^{n_s-2} + ... + s_{n_s}$
$G(x) = g_0x^{n_g} + g_1x^{n_g-1} + g_2x^{n_g-2} + ... + g_{n_g}$

Suppose that the polynomial degrees ($n_a$, $n_b$, $n_r$, $n_s$ and $n_g$) are chosen so that there is always at least one solution.

Is there any algorithm or method for this? I'm a computer programmer, and I'm going to implement this solution method by C++ code. I don't want to be lost in Mathematics; so please guide me to an easy-to-understand and practical method.

-
If the coefficient ring is a field then you can employ the extended Euclidean algorithm, e.g. see this answer. –  Bill Dubuque Feb 26 '12 at 21:09

Assuming $A$, $B$, and $G$ are given, this is just a system of linear equations for the unknown coefficients of $R$ and $S$. Can you program the solution to a system of linear equations?

-
Yes, that is the easiest and most feasible idea for now: en.wikibooks.org/wiki/Control_Systems/… –  hkBattousai Feb 26 '12 at 23:41
Besides the degree conditions, a necessary condition is obviously also that gcd($A$, $B$) divides $G$.
As Z[x] is a Euclidean domain, can't you just use the Euclidean algorithm, as if the polynomials were integers? Then in the same way, from one polynomial solution, say $R_0$, $S_0$, to $A R + B S = 1$ the general solution to your equation is presumably $R_0 G + B T$, $S_0 G - A T$ for any polynomial $T$ (assuming you started by dividing out gcd($A$, $B$, $G$)).
$\mathbb{Z}[x]$ isn't a Euclidean domain. $R[x]$ is a Euclidean domain if and only if $R$ is a field. Certainly you can use the Euclidean algorithm over $\mathbb{Q}$ or $\mathbb{R}$ though. –  Brandon Carter Feb 26 '12 at 20:27