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₁₁x₁ + ⋯ + a_1nx_n ≡ b₁ (mod q₁)
.
.
.
a_m1x₁ + ⋯ + a_mnx_n ≡ b_m (mod q_m)

Let q = lcm(q₁,...,q_m), q = q_jr_j, b_ij = a_ijr_i and c_j = b_jr_j. Then we have the equivalent system of congruences

b₁₁x₁ + ⋯ + b_1nx_n ≡ c₁ (mod q)
.
.
.
b_m1x₁ + ⋯ + b_mnx_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₁,...,d_r,0,...,0), where r = rank(B) and d₁,...,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₁y₁ ≡ k₁ (mod q)
.
.
.
d_ry_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₁,...,Y_r of lengths e₁,...,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₁,...,y_r,y_r+1,...,y_n]^t, where y_i = Y_{i,z_i} and y_r+1,...,y_n are arbitrary (mod q).

If r = n, we get e₁···e_r solutions (mod q), otherwise we get e₁···e_rq^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