Take the 2-minute tour ×

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

share|improve this question
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}$. –  Dylan Moreland Feb 4 '12 at 16:02
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$. –  M.B. Feb 4 '12 at 16:03
Minus signs should be outlawed, they cause such problems. When you reached $\bar{2}+\bar{2}-\bar{2}$, the answer is immediate: $\bar{2}$. –  André Nicolas Feb 4 '12 at 16:14
@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.) –  André Nicolas Feb 4 '12 at 16:56
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). –  Gerry Myerson Feb 5 '12 at 0:05

1 Answer 1

Yeah, so if you want to construct addition and multiplication tables for $\mathbb{Z}_5$, one way is to do the following:

Write out the general forms of an element of each class. For instance, $ 5k,5k+1,5k+2,5k+3,5k+4$. Now, do additions and multiplications to construct the table that you want by looking at the resultant remainder mod 5. Now, after you do this, to do a row reduction, you reduce your numbers by writing them in that form. I.e take $\frac{n}{5}$, and look at its floor. This tells you k. Then, to get the equilivelence class, take $n-5k$ and you're done. Now, you can do this for positives and negitives. Next, when you clear a row by making the leading term a one, you look up in your table the inverse of whatever is the leading term, and multiply the row by it. Thankfully, $Z_5$ is a field, so you can always find an inverswe--except for zero, of course.

Note that to get general expressions for addition and multiplication mod n, you do the same thing but with n and k.

share|improve this answer

Your Answer


