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.

  • $\begingroup$ $\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. $\endgroup$ – anon Jan 29 '14 at 4:36
  • $\begingroup$ 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\;$ ... $\endgroup$ – DonAntonio Jan 29 '14 at 4:40
  • $\begingroup$ can $\mathbb{Z}_5$ include say -5? $\endgroup$ – ari Jan 29 '14 at 5:06
  • $\begingroup$ 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$). $\endgroup$ – 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.