Systems of Congruences

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.

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 $\integer_p$ is a field, for p prime, and linear algebra works fine over any field --- not just $\real$ and $\complex$ .)

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

$\eqalign{2x + 6y &= 1 \mod{7} \cr 4x + 3y &= 2 \mod{7} \cr}$

Write the system in matrix form:

$\left[\matrix{2 & 6 \cr 4 & 3 \cr}\right] \left[\matrix{x \cr y \cr}\right] = \left[\matrix{1 \cr 2 \cr}\right].$

The determinant of the coefficient matrix is $2\cdot 3 - 4\cdot 6 = -18 = 3 \mod{7}$ . In particular, it's nonzero mod 7, so the system has a solution. For a $2 \times 2$ system, it's easiest to use the formula for inverting a $2 \times 2$ matrix:

$\left[\matrix{a & b \cr c & d \cr}\right]^{-1} = (ad - bc)^{-1} \left[\matrix{d & -b \cr -c & a \cr}\right].$

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

$\left[\matrix{2 & 6 \cr 4 & 3 \cr}\right]^{-1} \left[\matrix{2 & 6 \cr 4 & 3 \cr}\right] \left[\matrix{x \cr y \cr}\right] = \left[\matrix{1 \cr 2 \cr}\right] \left[\matrix{2 & 6 \cr 4 & 3 \cr}\right]^{-1},$

$\left[\matrix{x \cr y \cr}\right] = 5\cdot \left[\matrix{3 & 1 \cr 3 & 2 \cr}\right] \left[\matrix{1 \cr 2 \cr}\right] = 5\cdot \left[\matrix{5 \cr 4 \cr}\right] = \left[\matrix{4 \cr 0 \cr}\right].$

Recall that $ad - bc = 3 \mod{7}$ . The inverse of 3 mod 7 is 5, since $3\cdot 5 = 1 \mod{7}$ . This explains the 5 in the second line.

The solution is

$x = 4 \mod{7}, \quad y = 0 \mod{7}.\quad\halmos$

Example. Solve

$\matrix{x & + & 2y & & & = & 4 & \mod{5}\cr 3x & + & y & + & z & = & 0 & \mod{5}\cr x & + & y & + & 2z & = & 3 & \mod{5}\cr}$

In this case, it's better to use row reduction.

$\left[\matrix{1 & 2 & 0 & 4 \cr 3 & 1 & 1 & 0 \cr 1 & 1 & 2 & 3 \cr}\right] \matrix{\longrightarrow \cr r_2 \to r_2 + 2r_1 \cr} \left[\matrix{1 & 2 & 0 & 4 \cr 0 & 0 & 1 & 3 \cr 1 & 1 & 2 & 3 \cr}\right] \matrix{\longrightarrow \cr r_3 \to r_3 + 4r_1 \cr} \left[\matrix{1 & 2 & 0 & 4 \cr 0 & 0 & 1 & 3 \cr 0 & 4 & 2 & 4 \cr}\right] \matrix{\longrightarrow \cr r_2 \leftrightarrow r_3 \cr} \left[\matrix{1 & 2 & 0 & 4 \cr 0 & 4 & 2 & 4 \cr 0 & 0 & 1 & 3 \cr}\right]$

$\matrix{\longrightarrow \cr r_2 \to 4r_2 \cr} \left[\matrix{1 & 2 & 0 & 4 \cr 0 & 1 & 3 & 1 \cr 0 & 0 & 1 & 3 \cr}\right] \matrix{\longrightarrow \cr r_1 \to r_1 + 3r_2 \cr} \left[\matrix{1 & 0 & 4 & 2 \cr 0 & 1 & 3 & 1 \cr 0 & 0 & 1 & 3 \cr}\right] \matrix{\longrightarrow \cr r_1 \to r_1 + r_3 \cr}$

$\left[\matrix{1 & 0 & 0 & 0 \cr 0 & 1 & 3 & 1 \cr 0 & 0 & 1 & 3 \cr}\right] \matrix{\longrightarrow \cr r_2 \to r_2 + 2r_3 \cr} \left[\matrix{1 & 0 & 0 & 0 \cr 0 & 1 & 0 & 2 \cr 0 & 0 & 1 & 3 \cr}\right]$

The solution is

$x = 0 \mod{5}, \quad y = 2 \mod{5}, \quad z = 3 \mod{5}.\quad\halmos$

Example. Solve

$\matrix{& + & 2y & + & 2z & = & 1 \mod{5} \cr 2x & + & y & & & = & 1 \mod{5} \cr 4x & + & 2y & & & = & 2 \mod{5} \cr}$

I'll do this by row reduction:

$\left[\matrix{0 & 2 & 2 & 1 \cr 2 & 1 & 0 & 1 \cr 4 & 2 & 0 & 2 \cr}\right] \matrix{\longrightarrow \cr r_1 \leftrightarrow r_3 \cr} \left[\matrix{4 & 2 & 0 & 2 \cr 2 & 1 & 0 & 1 \cr 0 & 2 & 2 & 1 \cr}\right] \matrix{\longrightarrow \cr r_1 \to 4r_1 \cr} \left[\matrix{1 & 3 & 0 & 3 \cr 2 & 1 & 0 & 1 \cr 0 & 2 & 2 & 1 \cr}\right] \matrix{\longrightarrow \cr r_2 \to r_2+3r_1 \cr} \left[\matrix{1 & 3 & 0 & 3 \cr 0 & 0 & 0 & 0 \cr 0 & 2 & 2 & 1 \cr}\right] \matrix{\longrightarrow \cr r_2 \leftrightarrow r_3 \cr}$

$\left[\matrix{1 & 3 & 0 & 3 \cr 0 & 2 & 2 & 1 \cr 0 & 0 & 0 & 0 \cr}\right] \matrix{\longrightarrow \cr r_2 \to 3r_2 \cr} \left[\matrix{1 & 3 & 0 & 3 \cr 0 & 1 & 1 & 3 \cr 0 & 0 & 0 & 0 \cr}\right] \matrix{\longrightarrow \cr r_1 \to r_1+2r_2 \cr} \left[\matrix{1 & 0 & 2 & 4 \cr 0 & 1 & 1 & 3 \cr 0 & 0 & 0 & 0 \cr}\right]$

The equations are

$x + 2z = 4 \mod{5}, \quad y + z = 3 \mod{5}.$

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

$x = 3t + 4 \mod{5}, \quad y = 4t + 3 \mod{5}, \quad z = t \mod{5}.\quad\halmos$

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

$A = \left[\matrix{1 & 2 & 0 \cr 0 & 1 & 1 \cr 1 & 0 & 2 \cr}\right].$

To do this, tack on a copy of the $3 \times 3$ identity matrix, then row reduce the resulting $3 \times 6$ matrix. When the block on the left becomes the identity, the block on the right will have turned into $A^{-1}$ .

$\left[\matrix{1 & 2 & 0 & 1 & 0 & 0 \cr 0 & 1 & 1 & 0 & 1 & 0 \cr 1 & 0 & 2 & 0 & 0 & 1 \cr}\right] \matrix{\longrightarrow \cr r_3 \to r_3 + 2r_1 \cr} \left[\matrix{1 & 2 & 0 & 1 & 0 & 0 \cr 0 & 1 & 1 & 0 & 1 & 0 \cr 0 & 1 & 2 & 2 & 0 & 1 \cr}\right] \matrix{\longrightarrow \cr r_1 \to r_1 + r_2 \cr}$

$\left[\matrix{1 & 0 & 1 & 1 & 1 & 0 \cr 0 & 1 & 1 & 0 & 1 & 0 \cr 0 & 1 & 2 & 2 & 0 & 1 \cr}\right] \matrix{\longrightarrow \cr r_3 \to r_3 + 2r_2 \cr} \left[\matrix{1 & 0 & 1 & 1 & 1 & 0 \cr 0 & 1 & 1 & 0 & 1 & 0 \cr 0 & 0 & 1 & 2 & 2 & 1 \cr}\right] \matrix{\longrightarrow \cr r_1 \to r_1 + 2r_3 \cr}$

$\left[\matrix{1 & 0 & 0 & 2 & 2 & 2 \cr 0 & 1 & 1 & 0 & 1 & 0 \cr 0 & 0 & 1 & 2 & 2 & 1 \cr}\right] \matrix{\longrightarrow \cr r_2 \to r_2 + 2r_3 \cr} \left[\matrix{1 & 0 & 0 & 2 & 2 & 2 \cr 0 & 1 & 0 & 1 & 2 & 2 \cr 0 & 0 & 1 & 2 & 2 & 1 \cr}\right]$

Thus,

$A^{-1} = \left[\matrix{2 & 2 & 2 \cr 1 & 2 & 2 \cr 2 & 2 & 1 \cr}\right].\quad\halmos$

Example. Is the following matrix invertible mod 6?

$\left[\matrix{5 & 1 \cr 3 & 1 \cr}\right]$

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.

$\det \left[\matrix{5 & 1 \cr 3 & 1 \cr}\right] = 5 - 3 = 2.$

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 $(2,6) = 2 \ne 1$ , the matrix is not invertible. If you try to apply a standard matrix inversion algorithm to find the inverse, you'll find that it won't work.

Send comments about this page to: bikenaga@marauder.millersville.edu.

Last updated:

Bruce Ikenaga's Home Page

Math Department Home Page

Millersville University Home Page