O'Reilly logo

Fearless Symmetry by Robert Gross, Avner Ash

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

36 CHAPTER 4
At first glance, you might think that there is still a problem. After
all, we can write 1 · 5 0 · 5 (mod 5), but if we cancel the 5’s, we get
1 0 (mod 5). But this is not really a problem with our definition of
arithmetic modulo 5; we tried cancelling 5’s, and we were ignoring
the fact that 5 0 (mod 5). The rule is that we can only cancel
nonzero common factors, and “zero” does not mean equal to 0; it
means congruent to 0 when we are working with congruences.
Arithmetic Modulo a Prime
There is a special symbol used when working with the integers
modulo p (where p is any prime): F
p
. The letter F”herestands
for field.
DEFINITION: A field is a number system
5
where we can
divide by anything nonzero.
F
p
is defined as the set {0, 1, ..., p 1} with addition and mul-
tiplication defined as follows: If x, y,andz are in F
p
, x + y = z in
F
p
exactly when x + y z (mod p)andxy = z in F
p
exactly when
xy z (mod p). In other words, we allow ourselves to use equality
signs in F
p
where we would use congruence signs among integers.
We say that F
p
is a “field with p elements.” We also say that F
p
is a number system with characteristic p.
6
It is far from obvious
that F
p
is a field, because we need to rethink our usual definition
of division. F
p
does not contain fractions; rather, if x is any nonzero
element of F
p
, then there is some element y in F
p
so that xy = 1.
(In terms of congruences, this means that xy 1(modp).) Then to
“divide” by x, we instead multiply by y. In order for the number y
always to exist, it is essential that we use a prime modulus.
5
We are deliberately leaving the concept of “number system” vague. In this book, a
number system is a set made out of numbers so that all of the usual rules of algebra
hold, such as the commutative and associative laws of addition and multiplication, the
distributive law of multiplication over addition, and so on.
6
A field has characteristic p if a + a +···+a

p times
= 0foranyelementa in the field.
MODULAR ARITHMETIC 37
We can write out the addition and multiplication tables for any
specific prime p. We use the numerals from 0 to p 1forthe
elements of the field.
For example, addition and multiplication in F
2
look like this:
+
01
0 01
1
10
×
01
0 00
1
01
The first table means that 0 + 0 0 (mod 2), 0 + 1 1(mod2),
1 + 0 1(mod2), and 1+ 1 0 (mod 2). This is the same as
saying about whole numbers:
Even plus even is even. Even plus odd is odd.
Odd plus even is odd. Odd plus odd is even.
The second table means that 0 · 0 0 (mod 2), 0 · 1 0(mod2),
1 · 0 0(mod2), 1· 1 1 (mod 2). This is the same as saying
about whole numbers:
Even times even is even. Even times odd is even.
Odd times even is even. Odd times odd is odd.
As you probably know, computers use this binary arithmetic in
their innermost guts (or brains, depending on how you think of
computers.)
EXERCISE: Write out the addition and multiplication tables
for F
5
. Remember that every integer outside of the range 0–4
must be replaced by its remainder modulo 5.
SOLUTION: We have
+
01234
0 01234
1
12340
2 23401
3
34012
4
40123
×
01234
0 00000
1
01234
2 02413
3
03142
4
04321
For example, to explain the entry in the second table for the
spot in the row labeled 3 and the column labeled 4, we

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required