# Solve a system of linear congruences

I have this system:

\begin{align} a_{11} x_1 + a_{12} x_2 + \ldots + a_{1n} x_n &= b_1 \mod p \\ a_{21} x_1 + a_{22} x_2 + \ldots + a_{2n} x_n &= b_2 \mod p \\ \vdots \\ a_{n1} x_1 + a_{n2} x_2 + \ldots + a_{nn} x_n &= b_n \mod p \\ \end{align}

Can I solve it using ordinary Gaussian elimination? It seems to be incorrect to multiply a row by a constant, and then add or subtract this row with another, right?

If Gaussian elimination can't be applied here, then what other technique can I use?

-

## migrated from stackoverflow.comJun 6 '13 at 14:31

This question came from our site for professional and enthusiast programmers.

When p is a prime number, the integers modulo p still form a field (as the rationals and the reals do).

The Gaussian elimination works over any field, so in this case as well. Just be sure that you understand how to invert elements mod p and how to test for zero mod p.

For general p (that is, p is not a prime number), you can still make something similar to Gaussian elimination. Just bring your coefficient matrix into Smith normal form over the integers, which is a diagonal matrix. This makes solving the resulting equations mod p trivial.

The Smith normal form is described here, for example: https://en.wikipedia.org/wiki/Smith_normal_form.

The problem is even solvable in case the modulus on the right hand side is not the same for each equation. Given $$a_{11} x_1 + \dots + a_{1m} x_m = b_1 \pmod {p_1} \\ \vdots\\ a_{n1} x_1 + \dots + a_{nm} x_m = b_n \pmod {p_n},$$ rewrite the system as $$a_{11} x_1 + \dots + a_{1m} x_m + p_1 y = b_1 \\ \vdots\\ a_{n1} x_1 + \dots + a_{nm} x_m + p_n y = b_n,$$ which is in the variables $x_1, \dots, x_n, y$. Solve this system over the integers (using Smith normal form). Finally project the resulting solutions $(x_1, \dots, x_n, y)$ to $(x_1, \dots, x_n)$.

-
Upvoted, but I don't understand why should p be prime to form a field, what does it mean? – Alcott Jun 6 '13 at 13:21
A commutative ring is an algebraic structure where you can do addition and multiplication and where those operations obey the usual rules, e.g. the commutativity laws and the distributivity law. Examples of rings are the integers, the reals and the integers modulo n. A field is a special type of a commutative ring, namely where an element in multiplicatively invertible if and only if it is non-zero. This is true for the rationals or the reals where you are allowed to divide by an element if and only if it is non-zero, so both for a field... (to be continued) – Marc Jun 6 '13 at 13:29
... It is not true for the integers, e.g. 2 can not be inverted in the integers as there is no integer x with 2 * x = 1. The integers mod n usually do not form a field either: E.g. consider the case n = 6. Then 2 * 3 = 0 mod n. Therefore, neither 2 nor 3 can possess an inverse although both are zero. For n a prime number p, however, the integers mod p do form a field. Take p = 5, for example. A multiplicative inverse for, say, 2 is given by 3 because 2 * 3 = 1 mod 5. – Marc Jun 6 '13 at 13:31
... The reason for this is the Euclidean algorithm. If a is non-zero mod p, this means that p does not divide a, that is the gcd of a and p is 1. The Euclidean algorithm (performed in the integers) yield integers s and t such that 1 = s a + t p. It follows that s is a multiplicative inverse for a mod p. – Marc Jun 6 '13 at 13:33
Thank you so much, although it'll take some efforts for to digest your explanation, ;-). By form a field, you mean there indeed are solutions for a problem? – Alcott Jun 6 '13 at 13:34