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?
 A: 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)$.
