An Efficient Incremental Algorithm for Solving Systems of Linear Diophantine Equations

Évelyne Contejean and Hervé Devie

Abstract: In this paper, we describe an algorithm for solving systems of linear Diophantine equations based on a generalization of an algorithm for solving one equation due to Fortenbacher [1]. It can solve a system as a whole, or be used incrementally when the system is a sequential accumulation of several subsystems. The proof of termination of the algorithm is difficult, whereas the proofs of completeness and correctness are straightforward generalizations of Fortenbacher’s proof.


M. Clausen and A. Fortenbacher. Efficient solution of linear diophantine equations. Journal of Symbolic Computation, 8(1&2):201–216, 1989.

This document was translated from LATEX by HEVEA.