# Linear Diophantine Equations

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

 (1)

where are given in and where are unknowns in .

Theorem 1   Let be an Euclidean domain and let such that . We consider the linear Diophantine equation

 (2)

Then the following hold
Equation (2) has a solution if and only if divides .
If and if is a solution of Equation (2) then every other solution is of the form

 (3)

If where is a field, , and if Equation (2) is solvable, and if we have

 (4)

then there is a unique solution of Equation (2) such that

 (5)

Proof. First we prove . If is a solution of Equation (2), then which divides , divides also . Conversly, we assume that divides . The claim is trivial if . (Indeed, this implies and also .) Otherwise, let be computed by the Extended Euclidean Algorithm applied to , such that we have . Then is a solution of Equation (2).

Now we prove . Assume and let is a solution of Equation (2). Since , then and are coprime. Let be in . Then we have

Finally, we prove . Let be a solution of Equation (2). Let and be the quotient and the remainder of w.r.t. . Hence we have

 (6)

We define

 (7)

Observe that

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

Therefore we have

This proves the existence. Let us prove the unicity. Let be a solution of Equation (2). We know that there exists such that . Since holds, if , we have

This implies the uniquemess.

Theorem 2   Let be a commutative ring with identity element and let . ...

Marc Moreno Maza
2008-01-07