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
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
, we get a new set, with only
p − 1 elements, called F
, pronounced “eff-pea-cross.” It is
a group under multiplication. The neutral element is 1.
Every element a has an inverse. Because F
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
3x ≡ 1 (mod 7). Trial-and-error shows that x = 5. So 3
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.