- Systems of linear congruences relative to prime moduli can be solved by methods from linear algebra --- e.g. matrix inversion, Cramer's rule, or row reduction. You can also use results on linear Diophantine equations.

* Systems of linear congruences* can be solved
using methods from linear algebra: Matrix inversion, Cramer's rule,
or row reduction. In case the modulus is prime, everything you know
from linear algebra goes over to systems of linear congruences. (The
reason is the is a * field*, for p prime, and linear algebra works fine
over any field --- not just and .)

It's also possible to convert a system to a linear Diophantine equation.

I will stick to prime moduli for simplicity. I'll assume that you know some linear algebra, even if you haven't seen it done with modular arithmetic.

In the first example, I'll use the well-known fact that a matrix is invertible if and only if its determinant is nonzero.

* Example.* Solve

Write the system in matrix form:

The determinant of the coefficient matrix is . In particular, it's nonzero mod 7, so the system has a solution. For a system, it's easiest to use the formula for inverting a matrix:

If I apply this formula to the coefficient matrix for the system, I get

The inverse of 3 mod 7 is 5, since .

All I have to do is multiply both sides of the equation *on the
left* by the inverse of the coefficient matrix:

The solution is

In some cases, you can convert a system to a linear Diophantine equation, which we already know how to solve.

* Example.* Solve the following system over
:

Note that . Hence, I can't solve this system by matrix inversion or Cramer's rule.

Note, however, that the first equation is 4 times the second:

So it suffices to solve

This is equivalent to the Diophantine equation

Let . This gives

The general solution is

z is just a helper variable, so ignore it. Using the w-equation, I have

The general solution is

Recall that the original system was mod 7:

Note that this is a parametrized solution.

Here's another possibility. Suppose the system had been

As before, multiplying the second equation by 4 gives

But the two equations now imply " ", and this contradiction implies that the system has no solutions.

* Example.* Solve

With a system this large, it's better to use row reduction.

The solution is

* Example.* Solve

I'll do this by row reduction:

The equations are

There are multiple solutions --- in fact, since there is one free variable (z), there will be 5 distinct solutions mod 5. As is customary when a system has multiple solutions, I'll write the solution in parametric form.

Set . Then , so (by adding to both sides). Likewise, , so . The solution is

* Example.* This example has little to do with
solving congruences; it's presented to point out that you can work
with matrices using modular arithmetic pretty much as usual. I'll
compute the inverse mod 3 of the matrix

Recall the algorithm for inverting a matrix by row-reduction: Put a copy of the identity matrix on the right of the original matrix, then row reduce the resulting matrix. When the block on the left becomes the identity, the block on the right will have turned into .

Thus,

* Example.* Is the following matrix invertible
mod 6?

When the modulus is not prime, results from linear algebra must be used with care. In this case, I'd like to use the determinant to tell whether the matrix is invertible.

Normally, a nonzero determinant means that the matrix is invertible.
However, mod n the criterion is that the determinant must be
*relatively prime* to n. Since , the matrix is not invertible. So, for
instance, if you try apply the standard matrix inversion algorithm to
find the inverse, you'll find that it won't work.

Copyright 2015 by Bruce Ikenaga