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

In this chapter we start to develop s ome elementary
number theory. Modular arithmetic is sometimes taught
in elementary school as “clock arithmetic, ” and is of
fundamental importance in all of number theory. Modular
arithmetic gives us our ﬁrst examples of number systems
other than the usual ones, and also gives new examples of
groups.
The role of modular arithmetic in solving equations
will be introduced brieﬂy at the end of the chapter. This
role will continue, sometimes in surprising ways, as our
journey continues.
Cyclical Time
Modular arithmetic was invented and given that name by the
nineteenth-century German mathematician Carl Friedrich Gauss,
but the basic concept must be far older. It washed into American
grade schools on the wave called “The New Math” in the 1950s and
1960s, and may still be found in some schools. The basic idea was
usually illustrated by a problem of the following sort:
EXERCISE: Today is Tuesday. What day of the week will it be
25 days from now?
32 CHAPTER 4
The student is supposed to realize that there are 7 days in a
week: She can write 25 as 7 + 7 + 7 + 4, and then ignore all but the
4, and conclude that 25 days from now it will be Saturday, the same
as4daysfromnow.
Another typical problem concerned clocks:
EXERCISE: If an (analog) clock is now showing 8 o’clock,
what time will it be showing 33 hours from now?
The student is supposed to realize that clocks repeat themselves
every 12 hours.
1
So 33 hours from now is 12 + 12 + 9 hours from
now, which (for the clock) is the same as 9 hours from now. That
would mean the c lock shows 17 o’clock, but we have to drop another
12 and get 5 o’clock.
If this type of word problem were the only reason to study
modular arithmetic, we would not bother with it here. Rather,
these problems illustrate a powerful general concept that will be
critically important later. We stick to the clock example and use it
to illustrate some notation. We have decided that 17 o’clock is just
a synonym for 5 o’clock, and in general we can ignore any multiples
of 12 we run into. Computer scientists have a compact notation for
this: They write 17%12 = 5. The notation a%12” means “divide a
by 12 and compute the remainder.”
There is a problem here: In dealing with clocks, we use the
numbers 1 to 12, whereas remainders go from 0 to 11. In other
words, 24%12 = 0. This convention is in fact followed in 24-hour
time, which runs from 0:00 to 23:59.
Similarly, we can talk about minutes past the hour by dividing
by 60 and computing the remainder. For example, 74%60 = 14; if
the minute-hand of the clock is at 13 now, in 74 minutes it will be
at 13 + 14 = 27.
1
Digital clocks do not change the problem that much; they repeat every 24 hours,
assuming that they distinguish
AM from PM.

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