4
$\begingroup$

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

  • 0
    @Fabian: thanks for the helpful tips2011-04-17

2 Answers 2

6

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

  • 0
    @Gerry: thanks for the explanation. I had copied that notation from Paul R. Halmos -Linear Algebra Problem Book... But, yeah I will definitely try to avoid using those sorts of fractions in the future.2011-04-17
4

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