5
$\begingroup$

How to calculate with residue classes in $\mathbb{Z}{/5\mathbb{Z}}$?

  • $- \overline x \neq \overline x$ but $- \overline x = \overline{5-x}$
  • $\overline x + \overline y = \overline{x+y}$
  • $\overline x \cdot \overline y = \overline{x\cdot y}$

So the following calculation should be right?

$$ \overline 2 \cdot \overline 1 + \overline 2 \cdot \overline 1 - \overline 3 \cdot \overline 4 = \overline{2\cdot1} + \overline{2\cdot 1} - \overline{3\cdot4} = \overline{2\cdot1 + 2\cdot 1 - 3 \cdot 4} = \overline{-8} = \overline{-3} = \overline{5-3} = \overline{2} $$


How to use this, when solving a LES like the following with coefficients in $\mathbb{Z}_{5}$?

$$ \left( \begin{array}{cccc|c} 3 & -1 & 0 & 2 & -4\\ 1 & 0 & -3 & 2 & 2\\ 2 & 2 & -3 & 0 & 1\\ \end{array} \right) \rightsquigarrow \left( \begin{array}{cccc|c} 0 & -1 & 9 & -4 & -10\\ 1 & 0 & -3 & 2 & 2\\ 0 & 0 & 3 & -4 & -1\\ \end{array} \right) $$

Can I run the Gaussian algorithm without taking to much care of the residue classes and convert the integers after I've finished the algorithm?

Don't multiply a row by 5 during the Gaussian algorithm

  • 3
    Why do you think that $-\bar x = \bar x$? Everything else looks alright, but $-\overline{12} = -\bar2 = \bar3 \neq \bar 2$. And in general, you will have $-\bar x = \overline{-x} = \overline{5 - x}$.2012-02-04
  • 0
    It is true modulo 2... It is not true that $-\bar{x} = \bar{x}$ for every $x$ (unless you are working in $\mathbb{Z}_2$.2012-02-04
  • 0
    Minus signs should be outlawed, they cause such problems. When you reached $\bar{2}+\bar{2}-\bar{2}$, the answer is immediate: $\bar{2}$.2012-02-04
  • 0
    Ah ... well that's the mistake! Thanks. So if I've got an linear equation system with koefficients in $\mathbb{Z}_{5}$ I can calculate as usually and take care of the residue class afterwards? But $- \bar x \new \bar x$.2012-02-04
  • 0
    So $-12 = -3\cdot 5 + 3$ therefore $\overline{-12} = \overline{3}$, right?2012-02-04
  • 1
    @meinzlein: Yes, it is $\bar{3}$, or (I hope this doesn't confuse you) $\overline{-2}$. Indeed you can do all the computations in the world of ordinary integers, and convert later. Formally, this is because of $\overline{u+v}=\bar{u}+\bar{v}$ and $\overline{uv}=\bar{u}\bar{v}$. But look for example at $\bar{6}^{100}$. It would be painful to calculate $6^{100}$ and take care of the residue class afterwards. Note instead that $\bar{6}=\bar{1}$, so the answer is $\bar{1}$. (There are many related real-world examples.)2012-02-04
  • 2
    There's one thing you can do with Gaussian elimination over the integers (or the rationals, or the reals) that you can't do over ${\bf Z}_5$, and that is multiply a row by 5 (or any multiple of 5).2012-02-05
  • 0
    I see otherwise I get a zero row..2012-02-05
  • 0
    For a walkthrough example see [my answer here](http://math.stackexchange.com/a/86367/11619). Unfortunately that is modulo 29 as opposed to 5, so the numbers are a bit trickier. It might help you to understand, how the logic of the elementary operations is the same over **any** field.2012-05-29

1 Answers 1