Why Gaussian Elimination only works over field? When I was solving system of linear congruences (n variables, n equations), like this:
$AX \equiv b \pmod p$
I was told that ordinary Gaussian Elimination works if $p$ is prime. And I figured out that when $p$ is prime, integers $\pmod p$ form a field, otherwise it doesn't form a field, but a ring.
Here comes my problem, why Gaussian Elimination does not work over a ring? AFAIK, the difference between a ring and a field, is that elements in a field are multiplicatively invertible, but does it have something to do with the applicability of Gaussian Elimination? If yes, how?
 A: You need to be able to invert the element on the main diagonal (as long as it is non-zero).  If $p$ is not prime, you may not be able to do this.  For example, let $p=6$, then $2,3$ have no inverse.  So try $$\begin {pmatrix} 2&0\\0&3 \end {pmatrix}\begin {pmatrix} X_1 \\ X_2 \end {pmatrix}=\begin {pmatrix} 1 \\ 1 \end {pmatrix}\pmod 6$$
If you complain that the Gaussian elimination is done, change the $0$'s to $1$'s.  If $p$ is prime you are guaranteed an inverse of any non-zero element and the equation will be soluble.  Do it $\pmod 7$ and you will succeed.
A: There is a form of Gaussian elimination which works over a PID which is described in this article. The normal form you get from this algorithm (Smith normal form) consists of only diagonal entries which divide successively and is useful for getting information about the structure of f.g. modules over a PID.
A: To ensure that the solution set is preserved, the row operations should be reversible.  In a ring, the following operations are reversible:


*

*interchange two rows;

*add a multiple of one row to another row;

*multiply a row by a unit, that is, by an invertible element of the ring.


In a PID these suffice to put the matrix in row echelon form, but it is not always possible to put the matrix in reduced row echelon form since it is not always possible to obtain $1$ as a leading coefficient.  In particular, if a leading coefficient is not invertible, then one cannot obtain $1$ as a leading coefficient.  In a field, of course, all non-zero elements are invertible.
Example: Reduce the matrix
$$\begin{bmatrix}6 & 3\\ 4 & 8\end{bmatrix}$$
modulo $10.$
We subtract row $2$ from row $1$ to obtain
$$\begin{bmatrix}2 & 5\\ 4 & 2\end{bmatrix},$$
and then subtract twice row $1$ from row $2$ to obtain
$$\begin{bmatrix}2 & 5\\ 0 & 2\end{bmatrix}.$$
In general, one may have to repeat several times, Euclidean-algorithm style, until all but one element in the first column is $0$.  There's not much more we can do at this point.  We can reduce the size of the element $5$ as much as possible by subtracting twice row $2$ from row $1$ to obtain
$$\begin{bmatrix}2 & 1\\ 0 & 2\end{bmatrix}.$$
One also needs to worry about the right side of the equation.  If the reduced equation is
$$\begin{bmatrix}2 & 1\\ 0 & 2\end{bmatrix}\begin{bmatrix}x\\ y\end{bmatrix}=\begin{bmatrix}a\\ b\end{bmatrix}$$
then there is no solution if $b$ is odd.  If $b$ is even, then there are two solutions.  For example, if $(a,b)=(5,6)$ then the solutions are $(x,y)\in\{(1,3),(6,3)\}.$
Another example:  Reduce the matrix
$$\left[\begin{array}{cc|c}5 & 3 & 8\\ 10 & 4 & 6\end{array}\right]$$
modulo $12.$
Subtract twice row $1$ from row $2:$
$$\left[\begin{array}{cc|c}5 & 3 & 8\\ 0 & 10 & 2\end{array}\right].$$
Multiply row $1$ by the multiplicative inverse of $5,$ which is $5:$
$$\left[\begin{array}{cc|c}1 & 3 & 4\\ 0 & 10 & 2\end{array}\right].$$
Again there's not a lot we can do from here.  We are free to multiply row $2$ by an invertible element, such as $5,$ as well.  This is useful since it reduces the size of the coefficient:
$$\left[\begin{array}{cc|c}1 & 3 & 4\\ 0 & 2 & 10\end{array}\right].$$
We can now subtract row $2$ from row $1$ to reduce the size of the element $3:$
$$\left[\begin{array}{cc|c}1 & 1 & 6\\ 0 & 2 & 10\end{array}\right].$$
There are two solutions:
$$\begin{bmatrix}1\\ 5\end{bmatrix},\quad\begin{bmatrix}7\\ 11\end{bmatrix}.$$
