4
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ What you need to show is that if addition and multiplication are defined modulo $7$, then GF($7$) satisfies the axioms of a field, not the other way around. $\endgroup$
    – saulspatz
    Sep 12, 2019 at 0:20
  • $\begingroup$ Welcome to Mathematics Stack Exchange. Are you familiar with modular arithmetic (when $n$ is prime)? $\endgroup$ Sep 12, 2019 at 0:33
  • $\begingroup$ "clearly this breaks arithmetic rules in Real numbers." How so? Which rule? $1 + 1$ still equals $2$. It will always equal $2$. It's just that in $GF(2)$ we have a rule that $2=0$. In the real numbers we don't have a rule that $2=0$. So this isn't breaking the rules of real numbers. It's just that this is adding more rules that don't actual exist with the reals. $\endgroup$
    – fleablood
    Sep 12, 2019 at 1:06
  • 1
    $\begingroup$ Four is defined as $1+1+1+1$ and Five is defined by $1+1+1+1+1$. So $4+1 = (1+1+1+1) + 1 = 1+1+1+1+1=5$. That's all there is to it. $\endgroup$
    – fleablood
    Sep 12, 2019 at 1:08

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you. This subtlety is exactly what I was looking for. Based on your answer, I understand that I could have a finite field GF(5) = {0,1, "element2", "element3", "element4"}, where the element "element2" itself doesn't even have to belong to N (element2 could be "a duck that quacks"), but rather, its "class number" or "subscript" has to be an integer..... (continued in next comment) $\endgroup$
    – Snowball
    Sep 12, 2019 at 2:07
  • $\begingroup$ And I know that since the "class values" or "subscripts" are obviously \in Z, thereby allowing me to do standard arithmetic operations 4+1=5 in my original question above, even outside of 0 to 4. So in GF(5), when we say 7=2, we’re really just saying that 7 and 2 are referring to the same element. Am I understanding you correctly? $\endgroup$
    – Snowball
    Sep 12, 2019 at 2:07
  • $\begingroup$ Yes. If you use equivalence classes as your definition, you're saying that $2$ and $7$ are equivalent to each other. $\endgroup$ Sep 12, 2019 at 5:53
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .