Q:

System of linear equations over $\mathbb{Z}_p$

Something like this:
$$
\begin{cases}
x_1+4x_4=1\\
x_1+2x_2+4x_3=3\\
2x_1+2x_2+x_4=1\\
x_1+3x_3=2
\end{cases}
$$
over $\mathbb{Z}_5$
I'm fine with solving it in regular $\mathbb{Z}$ but have no idea how to go about this -- perhaps using Guass-Jordan method.

A:

Gauss-Jordan is definitely a fine way to go.

We can add any scalar multiple of an equation to another.
We can multiply any equation by a non-$0$ constant (that is, by $1,2,3,$ or $4$ modulo $5$).
We can interchange any two equations.

This differs from what you're probably used to, in that "modulo $5$" means that we effectively treat $5$ as $0.$ For one thing, this means (for example) that $1+4=0\pmod5,$ so adding $1$ is effectively the same as subtracting $4,$ and vice versa. Note that this also means that $$2\cdot 3=6=5+1=1\pmod{5}$$ and $$4\cdot 4=16=3\cdot 5+1=1\pmod{5}.$$ Hence,

multiplication by $3$ is effectively division by $2,$
multiplication by $2$ is effectively division by $3,$ and
multiplication by $4$ is effectively division by $4.$

For an example to see how this works, let's multiply the second equation by $3$: $$3x_1+6x_2+12x_3=9\\3x_1+(5+1)x_2+(2\cdot 5+2)x_3=5+4\\3x_1+x_2+2x_3=4$$ So, those that already had a factor of $2$ lost a factor of $2,$ while those that didn't gained a factor of $3$ (at least temporarily).

