Linear Diophantine Equations

Definition 1   Let $R$ be a commutative ring with identity element. A linear Diophantine equation over $R$ is an equation of the form

$$f_1 s_1 + \cdots + f_n s_n = a$$ (1)

where $f_1, \ldots, f_n, a$ are given in $R$ and where $s_1, \ldots, s_n$ are unknowns in $R$ .

Theorem 1   Let $R$ be an Euclidean domain and let $f,g,h, a \in R$ such that $h = {\gcd}(f,g)$ . We consider the linear Diophantine equation

$$s f + t g = a.$$ (2)

Then the following hold

$(i)$

Equation (2) has a solution if and only if $h$ divides $a$ .

$(ii)$

If $h \neq 0$ and if $(s_0, t_0) \in R^2$ is a solution of Equation (2) then every other solution is of the form

$$(s_0 + r \frac{g}{h}, t_0 - r \frac{f}{h}) \ \ {\rm where} \ \ r \in R.$$ (3)

$(iii)$

If $R = F[x]$ where $F$ is a field, $h \neq 0$ , and if Equation (2) is solvable, and if we have

$${\deg} f + {\deg} g - {\deg} h > {\deg} a$$ (4)

then there is a unique solution $(s_0, t_0) \in R^2$ of Equation (2) such that

$${\deg} s_0 < {\deg} g - {\deg} h \ \ {\rm and} \ \ {\deg} t_0 < {\deg} f - {\deg} h.$$ (5)

Proof. First we prove $(i)$ . If $(s_0, t_0) \in R^2$ is a solution of Equation (2), then $h$ which divides $s_0 f + t_0 g$ , divides also $a$ . Conversly, we assume that $h = {\gcd}(f,g)$ divides $a$ . The claim is trivial if $h = 0$ . (Indeed, this implies $f = g = 0$ and also $a = 0$ .) Otherwise, let $(s_0, t_0) \in R^2$ be computed by the Extended Euclidean Algorithm applied to $(f, g)$ , such that we have $s_0 f + t_0 g = h$ . Then $(s, t) = (s_0 a / h, t_0 a / h)$ is a solution of Equation (2).

Now we prove $(ii)$ . Assume $h \neq 0$ and let $(s_0, t_0) \in R^2$ is a solution of Equation (2). Since $h \neq 0$ , then $f / h$ and $g / h$ are coprime. Let $(s, t)$ be in $R^2$ . Then we have

$$\begin{array}{rcl} s f + t g = a & \iff & (s - s_0) f + (t - ... ... + r (g / h) \ \ {\rm and} \ \ t = t_0 - r (f / h). \end{array}$$

Finally, we prove $(iii)$ . Let $(s_1, t_1) \in R^2$ be a solution of Equation (2). Let $q$ and $t_0$ be the quotient and the remainder of $t_1$ w.r.t. $f / h$ . Hence we have

$$t_1 = f/h q + t_0 \ \ {\rm and} \ \ {\deg} t_0 < {\deg} f - {\deg} h.$$ (6)

We define

$$s_0 = s_1 + q g / h.$$ (7)

Observe that

$$(s_0, t_0) = (s_1, t_1) + q (g /h, - f /h)$$

solves Equation (2) too. By Relation (6) and by hypothesis we have

$${\deg} (t_0 g) < {\deg} f + {\deg} g - {\deg} h \ \ {\rm and} \ \ {\deg} a < {\deg} f + {\deg} g - {\deg} h$$

leading to

$${\deg} s_0 + {\deg} f = {\deg} s_0 f = {\deg} (a - t_0 g) < {\deg} f + {\deg} g - {\deg} h.$$

Therefore we have

$${\deg} t_0 < {\deg} f - {\deg} h \ \ {\rm and} \ \ {\deg} s_0 < {\deg} g - {\deg} h.$$

This proves the existence. Let us prove the unicity. Let $(s, t)$ be a solution of Equation (2). We know that there exists $r \in R$ such that $s = s_0 + r g / h$ . Since ${\deg} s_0 < {\deg} g - {\deg} h$ holds, if $r \neq 0$ , we have

$${\deg} s \geq {\deg} (g / h) = {\deg} g - {\deg} h.$$

This implies the uniquemess. $\qedsymbol$

Theorem 2   Let $R$ be a commutative ring with identity element and let $p \in R$ . ...