Algorithm 406.

The article presents information on linear equations using residue arithmetic. The subroutine EXACT solves the matrix equation AX = B for X, where A is an N by N integer matrix, B is an N by M integer matrix, and X is an N by M real matrix. Residue arithmetic is used to obtain the exact solution, consisting of the rational components of X, i.e. det(A) and the rounded solution, computed as the quotient of the rational components and stored in the array X. The subroutine can be used to solve systems of linear algebraic equations, to invert matrices, and to compute determinants and adjoint matrices. In the concept of residue modulo m refers to the least non-negative remainder of the integer x after division by m. The computation is performed by means of Gaussian elimination for residue arithmetic using the residue system. Subroutine EXACT was tested on a CDC 6600 computer on which the maximum size of integer variables which can be used in arithmetic operations is 48 bits. The maximum size of real variables is 48 bits with an 11-bit exponent.