# Subtraction and division with integers modulo 3

(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$?

-
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

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$.

-
@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

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$.

-
Thank you for this answer – ghshtalt Apr 17 '11 at 10:19