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.

Start Free Trial

No credit card required