### Solving a system of linear congruences with possibly differing moduli, using the Smith normal form (SNF) of an integer matrix

We solve the system of linear congruences:
a_{11}x_{1} + ⋯ + a_{1n}x_{n} ≡ b_{1} (mod q_{1})

.

.

.

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

Let q = lcm(q_{1},...,q_{m}), q = q_{j}r_{j}, b_{ij} = a_{ij}r_{i} and c_{j} = b_{j}r_{j}. Then we have the equivalent system of congruences
b_{11}x_{1} + ⋯ + b_{1n}x_{n} ≡ c_{1} (mod q)

.

.

.

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

We use the Smith normal form of the integer matrix B.
P and Q are unimodular matrices such that PBQ = diag(d_{1},...,d_{r},0,...,0), where r = rank(B) 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 = PC. Then we have the equivalent 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 e_{1},...,e_{r}, where e_{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 e_{1}···e_{r} solutions (mod q), otherwise we get e_{1}···e_{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.

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

*Last modified 13th June 2015*

Return to main page