A method is described for computing the exact rational solution to a regular systemAx=b of linear equations with integer coefficients. The method involves: (i) computing the inverse (modp) ofA for some primep; (ii) using successive refinements to compute an integer vector\(\bar x\) such that\(A\bar x \equiv b\) (modp^m) for a suitably large integerm; and (iii) deducing the rational solutionx from thep-adic approximation\(\bar x\). For matricesA andb with entries of bounded size and dimensionsn×n andn×1, this method can be implemented in timeO(n³(logn)²) which is better than methods previously used.

Authors and Affiliations

1. Department of Mathematics and Statistics, Carleton University, K1S 5B6, Ottawa, Canada

   John D. Dixon

This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (Grant No. A 7171)

Reprints and permissions