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

No credit card required 36 CHAPTER 4
At ﬁrst 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 deﬁnition 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 ﬁeld.
DEFINITION: A ﬁeld is a number system
5
where we can
divide by anything nonzero.
F
p
is deﬁned as the set {0, 1, ..., p 1} with addition and mul-
tiplication deﬁned 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 “ﬁeld 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 ﬁeld, because we need to rethink our usual deﬁnition
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 ﬁeld has characteristic p if a + a +···+a

p times
= 0foranyelementa in the ﬁeld. MODULAR ARITHMETIC 37
We can write out the addition and multiplication tables for any
speciﬁc prime p. We use the numerals from 0 to p 1forthe
elements of the ﬁeld.
For example, addition and multiplication in F
2
look like this:
+
01
0 01
1
10
×
01
0 00
1
01
The ﬁrst 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
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
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.

No credit card required