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

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

Start Free Trial

No credit card required