### Solving a system of linear congruences using the Smith normal form (SNF) of an integer matrix

A is a nonzero m × n matrix of integers, B is m × 1, X is n × 1. We solve the system of linear congruences AX ≡ B (mod q):
a_{11}x_{1} + ⋯ + a_{1n}x_{n} ≡ b_{1} (mod q)

.

.

.

a_{m1}x_{1} + ⋯ + a_{mn}x_{n} ≡ b_{m} (mod q)

using the Smith normal form of the integer matrix A.
P and Q are unimodular matrices such that PAQ = diag(d_{1},...,d_{r},0,...,0), where r = rank(A) and d_{1},...,d_{r} are positive integers such that d_{i} divides d_{i+1} for 1 ≤ i ≤ r-1.

Write X = QY and K = PB. Then AX ≡ B (mod q) is equivalent to the system of congrences

d_{1}y_{1} ≡ k_{1} (mod q)

.

.

.

d_{r}y_{r} ≡ k_{r} (mod q)

0 ≡ k_{r+1} (mod q)

.

.

.

0 ≡ k_{n} (mod q).

Assuming that the first r congruences are soluble (mod q) with solution arrays Y_{1},...,Y_{r}
of lengths c_{1},...,c_{r}, where c_{i} = gcd(d_{i},q) and that the last n-r congruences are satisfied,
we get the complete solution of the form

X = QY, where Y = [y_{1},...,y_{r},y_{r+1},...,y_{n}]^{t},
where y_{i} = Y_{i,zi} and y_{r+1},...,y_{n} are arbitrary (mod q). If r = n, we get c_{1}···c_{r} solutions (mod q), otherwise we get c_{1}···c_{r}q^{n-r} solutions (mod q).

The augmented matrix [A|B] can be entered either

(i) as a string of m(n+1) integers separated by spaces, or

(ii) cut and pasted from a text file, with entries separated by spaces and each row ended by a newline.

We assume that [A|B] is not the zero matrix (mod q).

The author is grateful to Alan Offer for programming assistance with the recursive construction of the cartesian product.

*Last modified 10th June 2015*

Return to main page