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

$ AR + BS = G $


$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.


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?


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$)).

  • 3
    $\begingroup$ $\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. $\endgroup$ – Brandon Carter Feb 26 '12 at 20:27
  • 1
    $\begingroup$ You can use the Euclidean algorithm over the integers if you modify it by occasionally multiplying through by some power of a leading coefficient to make sure everything stays in the integers. $\endgroup$ – Gerry Myerson Feb 26 '12 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.