Basic Arithmetic in Finite Fields

Question

I have just begun studying finite fields today, and it is clear in GF(2) why 1+1=0. (I just show that 1+1 can't equal 1, or 1=0, which contradicts an axiom that states that 1 is not 0).

If we interpreted these symbols "1", "+", "1", "0" as we would in primary school, clearly this breaks arithmetic rules in Real numbers.

Given that, I have lost all confidence in how arithmetic can be applied in a finite field. How do I even know how to do basic arithmetic on GF(n) where n is prime? For example, for GF(7), how do I even know that 4+1=5? Can anyone show with just the 9 axioms of finite fields that 4+1=5?

Axioms: associativity of addition, additive identity, additive inverse, commutatitivity of addition, associativity of multiplication, multiplicative inverse, commutatitivity of mulitplication, distributive law

Answer 1

This actually brings up a subtle point. What do we mean by $5$ in a finite field? Or if you choose to define $5$ in terms of $1 ~(5=1+1+1+1+1)$, then what do we mean by $1$?

One answer is to define $5$ in terms of equivalence classes. Say that two integers $m$ and $n$ are equivalent if $p \vert (m-n).$ First, you prove this really is an equivalence relation on the integers. Then you define $[m]+[n]=[m+n]$ and $[m][n]= [mn]$. So by $5$ we actually mean the equivalence class $[5]$.

You need to prove that your field operations are well-defined (you get the same answer no matter which representative of an equivalence class you choose) and that $[0]$ and $[1]$ really are the additive and multiplicative identities, as you'd expect. But once you've done that, you can see that $[4]+[1]=[5]$ (and usually we abuse notation by dropping the brackets) because we've defined it that way.

Answer 2

There’s really no big deal. You are really working in integers (never in the reals), and whenever you get an answer that’s too big or too negative, subtract or add a multiple of your prime number $n$ (conventionally, we call the modulus $p$ in these cases). So, if you’re working modulo $7$, to add $4+1$, you do it in the integers $\Bbb Z$. Answer $5$. Is it at least $7$? No, so just leave it be. But to add $4+5$, the integer sum is $9$, so you subtract $7$ to get $2$, and in the system of integers modulo $7$, you have $4+5=2$. A standard way of writing this is $4+5\equiv2\pmod7$, which you read, “four plus five is congruent to two modulo seven”. This notation and terminology goes back to Gauss (1801), maybe even farther.

Answer 3

Beneath it all... we count.

And it doesn't matter what we count; we just count.

So we define $4$ as what we get if we add $1$ a "tick-tick-tick-tick" number of times. And we define $5$ as what we get if we add $1$ a "tick-tick-tick-tick-tick" numbers of times.

Well every time we add $4$ to $5$ we always count $9$ times. THat's because if you put "tick-tick-tick-tick-tick" and then put another "tick-tick-tick-tick" you get "tick-tick-tick-tick-tick-tick-tick-tick-tick" which we define as what $9$ is.

It's just that in the finite field $GF(2)$ you know that $1+1 = 0$.

So you count

1 tick $\to 1$

2 tick $\to 1+1 = 0$

3 tick $\to 0+1 = 1$

4 tick $\to 1+1 = 0$.

5 tick $\to 0+1 = 1$.

Okay that was "tick-tick-tick-tick-tick". Now to add "tick-tick-tick-tick

1 tick $\to 1+1 =0$

2 tick $\to 0+1 = 1$

3 tick $\to 1+1 = 0$

4 tick $\to 0+1 = 1$.

So $5 +4$ still equals $9$. We just have $5 = 1$ and $4 = 0$ and $9=1$.

The only rule we've changed is "adding one gives us a new number we never had before". That rule tells us $9\ne 1$ but without it $9=1$ is perfectly acceptable.