# 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.

• $\Bbb Z/5\Bbb Z$ is a field (even better than a PID like $\Bbb Z$), so all of your usual knowledge of linear algebra applies, just with a different type of scalar. – anon Jan 29 '14 at 4:36
• Do exactly what you'd do with that system over $\;\Bbb Z\;$ except dividing by some multiple of $\;5\;$ , and at the end right all modulo $\;5\;$ ... – DonAntonio Jan 29 '14 at 4:40
• can $\mathbb{Z}_5$ include say -5? – ari Jan 29 '14 at 5:06
• You don't know what $Z_5$ is? If you don't you should go back and make sure you do first before going any further. To answer your question, yes it includes $-(1+1+1+1+1)$, but this is equal to $0$ (and you can't divide by $0$). – anon Jan 29 '14 at 5:10

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).