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.

(The integers modulo 3) permit unrestricted subtraction (so that, for example, $1-2=2$), and they permit division restricted only by the exclusion of the denominator 0 (so that, for example, $\frac{1}{2} = 2$).

Could someone please help me understand these operations on this finite field? I had a couple of thoughts about subtraction: if the numbers are arranged from left to right in increasing order and I "moved $2$ places to the left for subraction" I would get $2= 1-2$ (as confirmed in the book). This would imply that $0-2 =1$, which seems correct to me since $1+2 =3$... But I wasn't sure if this is the proper way to think about this... Is there a better way? With the division, I don't know: why is $\frac{1}{2} =2$?

Thank you for your help.

share|improve this question
1  
The division is "best" understood via its definition. The number $x=1/2$ is defined as the solution to $2x=1$. (in modular arithmetic this equation doesn't necessarily need to have a unique solution, but for mod $p$ with $p$ prime it does). –  Fabian Apr 17 '11 at 7:28
    
By the way, it is usually best to think about the numbers as being arranged on a circle. –  Fabian Apr 17 '11 at 7:29
    
@Fabian: thanks for the helpful tips –  ghshtalt Apr 17 '11 at 10:18
add comment

2 Answers

up vote 5 down vote accepted

The integers $\mathbb Z$ are a ring: That means it has addition, subtraction, multiplication and some axioms about them.

By $3 \mathbb Z$ I denote $\{ 3x \in \mathbb Z \mid x \in \mathbb Z \} = \{\cdots,-6,-3,0,3,6,\cdots\}$. The idea of modular arithmetic (mod 3) is that -6 = -3 = 0 = 3 = 6 = ... and ... = -5 = -2 = 1 = 4 = 6 = ... and so on.


The first step now is to make an equivalence relation $\sim$ that expresses this (i.e. $0\sim 3$, $2 \sim 8$, $1 \not \sim 5$) and this is quite easy! Define $x \sim y :\!\!\iff x + 3\mathbb Z = y + 3\mathbb Z$. Since all we have done is applied the function $\varphi(x) = x + 3\mathbb Z$ to both sides this is automatically an equivalence relation.

We can see that it is the one we want as well:

  • $0\sim 3 \iff 0 + 3\mathbb Z = 3 + 3\mathbb Z \iff \{\cdots,-6,-3,0,3,6,\cdots\} = \{\cdots,-3,0,3,6,9,\cdots\} \iff \text{true}$.
  • $2\sim 8 \iff 2 + 3\mathbb Z = 8 + 3\mathbb Z \iff \{\cdots,-4,-1,2,5,8,\cdots\} = \{\cdots,2,5,8,11,14,\cdots\} \iff \text{true}$.
  • $1\not\sim 5 \iff 1 + 3\mathbb Z \not = 5 + 3\mathbb Z \iff \{\cdots,-5,-2,1,4,7,\cdots\} \not = \{\cdots,-1,2,5,8,14,\cdots\} \iff \text{true}$.

We can now define arithmetic operations on the image $\varphi(\mathbb Z) = \mathbb Z / 3 \mathbb Z$.

  • $\varphi(a)+\varphi(b):=\varphi(a+b)$
  • $-\varphi(a):=\varphi(-a)$
  • $\varphi(a)\cdot \varphi(b):=\varphi(a\cdot b)$

To see that e.g. + is actually a function it is necessary to prove that it "respects the equivalence relation" in the sense that if $\varphi(x) = \varphi(x')$ and $\varphi(y) = \varphi(y')$ then $\varphi(x) + \varphi(y) = \varphi(x') + \varphi(y')$. Here is a proof:

  • $(x + 3 \mathbb Z) + (y + 3 \mathbb Z) = \{\cdots,x-6,x-3,x,x+3,x+6,\cdots\}+ \{\cdots,y-6,y-3,y,y+3,y+6,\cdots\} = \{x+y+i+j\in \mathbb Z | i \in 3 \mathbb Z, j \in 3 \mathbb Z\} = (x + y) + 3 \mathbb Z$.

The same type of calculation proves that negation and multiplication are respectful functions.


Since the function is respectful it respects each of the ring axioms, this proves that $\mathbb Z/3 \mathbb Z$ is a ring and $\varphi$ is a ring homomorphism. It should be clear that nothing depends on special properties of the number 3 so far and the arguments above are fully general.

The standard notation for working in this ring is not $\varphi(x) = \varphi(y)$ but $x \equiv y \pmod 3$ where $x$ is implicitly mapped from $\mathbb Z$ to $\mathbb Z / 3 \mathbb Z$ if needed.

The fact that it is furthermore a field is quite miraculous and depends the fact that 3 is a prime number. For $p$ prime every nonzero element of $\mathbb Z/p \mathbb Z$ is invertible. The proof of this depends on details from number theory rather than algebra. First the condition for a number $x$ to be invertible (in any ring) is that there exists some number $x^{-1}$ such that $x \cdot x^{-1} = 1$. In the ring of rationals $\mathbb Q$ this number is $\frac{1}{x}$ (the rationals are also a field because $1 \not = 0$ and every nonzero element is invertible).


Given $(a,b)=1$, that is, $a$,$b$ coprime there exists $x$,$y$ such that $ax + by = 1$. You can compute this by the Euclidean algorithm. In terms of modular arithmetic this tells us that given $(a,b) = 1$ then there exists $x$ such that $ax \equiv 1 \pmod b$! Of course when "b" is prime every element except 0 is coprime and thus has an inverse. Since $1 \not \equiv 0 \pmod p$ this proves that $\mathbb Z/p \mathbb Z$ is a field too.


Now we can compute $2^{-1} \pmod 3$, it must be the unique number $\varphi(x)$ such that $2x + 3y = 1$, $x = 2, y = -1$ will do so we have $2^{-1} \equiv 2 \pmod 3$.

share|improve this answer
    
@quanta: thank you for the answer. I'm still digesting it, but I wanted to check if I am understanding part of the idea. If I wanted to divide on say integers modulo 5 (where there are a couple more examples) then for say $\frac{3}{4}=x$ I would first always calculate $4^{-1}$ and then multiply? And because of the gcd stuff you showed, I know that $1\equiv 4x \mod 5 \Rightarrow x = 4 \Rightarrow \frac{3}{4} = 2$? So in these cases it is about finding the inverses first? –  ghshtalt Apr 17 '11 at 9:44
    
@quanta: ok, yeah I meant by that 3 divided by 4 in integers modulo 5 (and I realize the way I used $x$ in my above comment was nonsense). But isn't that how you would carry out division of 3 by 4 in integers modulo 5? Since $4$ is the inverse of $4$, $3*4^{-1}=2$ in integers modulo 5, no? –  ghshtalt Apr 17 '11 at 9:53
    
In general modular arithmetic the use of fractions is a mistake but even though prime modulus gives a field there is not homomorphism from $\mathbb Q$ to $\mathbb Z/p \mathbb Z$ so every fraction is not meaningful (consider $1/2 \pmod 2$). Overall I don't think the fraction is a useful concept in modular arithmetic. –  quanta Apr 17 '11 at 9:55
    
"3 divided by 4" or "3/4" could be used to mean $3 \cdot 4^{-1}$ or anything you like. I find it easier to avoid completely but of course just do it whatever way you like. –  quanta Apr 17 '11 at 9:56
    
@quanta: I'm sorry if I'm just completely missing something here, but are you saying there is a problem with the way I am trying to write down/express an idea, or with the idea itself that I am trying to carry out division on the integers modulo 5? –  ghshtalt Apr 17 '11 at 10:00
show 3 more comments

Do you understand multiplication in the field? If so, then division's easy; $a/b=c$ means $a=bc$. In particular, $1/2=2$ because $2\times2=1$.

If you don't understand multiplication in the field, just let me know, I'll try something else.

Oh, and if you understand addition, then you understand subtraction, because $a-b=c$ means $a=b+c$.

share|improve this answer
    
Thank you for this answer –  ghshtalt Apr 17 '11 at 10:19
add comment

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.