 |
|
|
|
|
 |
 |
|
The Solution of Linear Equations with Integer Coefficients Using Modular Arithmetic and Cramer's Rule
|
|
|
|
|
|
| Organization: | University of Massachusetts Lowell |
| Department: | Mathematical Sciences |
|
|
|
|
|
|
| Mathematica in Education and Research |
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
 |
|
|
| 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 |
|
|
For the newest resources, visit Wolfram Repositories and Archives »
