MODULAR ARITHMETIC 39

modulo 13. Because of the symmetry of the table, after we

had done the seventh row we could then get the others

without any more work. The last row is just the reverse o f the

second row, for example.

There are ﬁelds that contain a composite number of elements .

The number of elements in any ﬁnite ﬁeld is always a power of

a prime. Fields with composite numbers of elements are relevant

to the type of number theory we are exploring, but they are too

difﬁcult for the level of this chapter. We will not need them in this

book, but it is worth mentioning that they can be deﬁned.

Modular Arithmetic and Group Theory

One thing mathematicians do is connect concepts that occur in

different trains of thought. In the ﬁrst few chapters, we were

concerned with groups. In this chapter, we have discussed modular

arithmetic, which is our wa y of dealing with divisibility of numbers

and remainders . We can connect these concepts by noticing that

modular arithmetic gives us not one but two groups for each

prime p:

1. F

p

is a group under addition. The neutral element is 0. The

inverse of any number a (mod p)isjustp − a (mod p).

2. If we throw 0 away from F

p

, we get a new set, with only

p − 1 elements, called F

×

p

, pronounced “eff-pea-cross.” It is

a group under multiplication. The neutral element is 1.

Every element a has an inverse. Because F

p

is a ﬁeld, to

ﬁnd the inverse of a,yousolveax ≡ 1(modp)by

“dividing” both sides by a.

For example, to ﬁnd the inverse of 3 in F

×

7

,wehavetosolve

3x ≡ 1 (mod 7). Trial-and-error shows that x = 5. So 3

−1

= 5inF

×

7

.

Solving this congruence for large moduli without using trial-and-

error requires a tool called the Euclidean algorithm, which we will

not need in this book.

40 CHAPTER 4

No matter what the prime p is, these two groups are “commuta-

tive”—that is, the group law satisﬁes x + y = y + x in the ﬁrst case

and x · y = y · x in the second. So these groups are different from,

and rather simpler than, SO(3) and

n

.

7

The groups F

p

and F

×

p

(no matter what p is) also share a strong

property that again fails to hold for SO(3) and for

n

if n > 2. They

are cyclic.

DEFINITION: Agroupiscyclic if it contains some element,

call it g, so that we can get every non-neutral element of the

group by repeating the group composition on g or g

−1

.This

particular element g is called a generator of the group.

The group F

p

is cyclic because starting with g = 1, we get 1,

1 + 1 ≡ 2, 1 + 1 + 1 ≡ 3, ..., until we get all the elements of F

p

.

The group of ordinary integers with group operation addition

(and neutral element 0) is also cyclic, generated by g = 1, because

any positive integer is a sum of 1’s, and any negative integer is a

sum of −1’s.

The fact that F

×

p

is cyclic is very interesting but would take us too

long to prove here. You can check it for any particular prime p.For

instance, if p = 5, starting with g = 2, we get 2, 2 · 2 ≡ 4(mod5),

2 · 2 · 2 ≡ 3(mod5),and2· 2 · 2 · 2 ≡ 1(mod5).

EXERCISE: Show that F

×

17

is cyclic.

SOLUTION: We use trial-and-error. We start by seeing if 2

might be a generator of the group: 2

1

≡ 2, 2

2

≡ 4, 2

3

≡ 8,

2

4

≡ 16, 2

5

≡ 15, 2

6

≡ 13, 2

7

≡ 9, and 2

8

≡ 1, and now the

pattern repeats: 2

9

≡ 2, 2

10

≡ 4, etc. So we do not encounter

every element of F

×

17

by taking powers of 2.

Next, we try 3: 3

1

≡ 3, 3

2

≡ 9, 3

3

≡ 10, 3

4

≡ 13, 3

5

≡ 5,

3

6

≡ 15, 3

7

≡ 11, 3

8

≡ 16, 3

9

≡ 14, 3

10

≡ 8, 3

11

≡ 7, 3

12

≡ 4,

3

13

≡ 12, 3

14

≡ 2, 3

15

≡ 6, and 3

16

≡ 1. This shows that 3 is a

generator of F

×

17

.

7

n

is short for the permutation group

{1,2,3,...,n}

.

Start Free Trial

No credit card required