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₁₁x₁ + ⋯ + a_1nx_n ≡ b₁ (mod q)
.
.
.
a_m1x₁ + ⋯ + a_mnx_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₁,...,d_r,0,...,0), where r = rank(A) 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 = PB. Then AX ≡ B (mod q) is equivalent to the 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 c₁,...,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₁,...,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 c₁···c_r solutions (mod q), otherwise we get c₁···c_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.

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