## 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

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}
.

## 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