Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title Downloads

The Solution of Linear Equations with Integer Coefficients Using Modular Arithmetic and Cramer's Rule

Kenneth Levasseur
Organization: University of Massachusetts Lowell
Department: Mathematical Sciences
Journal / Anthology

Mathematica in Education and Research
Year: 1995
Volume: 4
Issue: 1
Page range: 14-18

The solution to a system of n linear equations in n unknowns with integer coefficients is generally rational and not necessarily integer. For this reason, it would not appear that the solutions to corresponding modular systems would be related. However, by a clever application of Cramer's Rule, the numerators and denominators of the solution to these systems can be obtained. The method also can make use of the Chinese Remainder Theorem for large systems. This method was published in Lipson [Lipson 1981], and with Mathematica, it becomes feasible. With Mathematica's capabilities, this method is not really efficient for ordinary systems, but it's a nice way to combine topics from linear algebra and number theory. For a truly huge system being solved on a computer with parallel processing capabilities the method outlined here might speed up the solution. This would be done by replacing a large modulus with many relatively small moduli and then combining the results using the Chinese Remainder Theorem.

*Mathematics > Algebra > Linear Algebra
Downloads Download Wolfram CDF Player

ModLS.nb (73.8 KB) - Mathematica Notebook

Files specific to Mathematica 2.2 version:
ModLS.ma (40.1 KB) - Mathematica Notebook 2.2 or older