Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

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?

share|cite|improve this answer
Yes, that is the easiest and most feasible idea for now:… – 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$)).

share|cite|improve this answer
$\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
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. – Gerry Myerson Feb 26 '12 at 23:07

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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