Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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
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}$. –  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
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.) –  André Nicolas Feb 4 '12 at 16:56
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). –  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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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