1.7. MODULAR ARITHMETIC

i

“bookmt” — 2006/8/8 — 12:58 — page 37 — #49

i

i

1.7. MODULAR ARITHMETIC

37

1.7. Modular Arithmetic

We are all familiar with the arithmetic appropriate to the hours of a clock:

If it is now 9 o’clock, then in 7 hours it will be 4 o’clock. Thus in clock arithmetic, 9 + 7 = 4. The clock number 12 is the identity for clock addition: Whatever time the clock now shows, in 12 hours it will show the same time. Multiplication of hours is not quite so familiar an operation, but it does make sense: If it is now 12 o’clock, then after 5 periods of seven hours it will be 11 o’clock, so 5  7 D 11 in clock arithmetic. Clock arithmetic is an arithmetic system with only 12 numbers, in which all the usual laws of arithmetic hold, except that division is not generally possible.

The goal of this section is to examine clock arithmetic for a clock face with n hours, for any natural number n. (We don’t do this because we want to build crazy clocks with strange numbers of hours, but because the resulting algebraic systems are important in algebra and its applications.)

Fix a natural number n > 1. Think of a clock face with n hours (la beled 0; 1; 2; : : : ; n 1) and of circumference n. Imagine taking a number line, with the integer points marked, and wrapping it around the circumference of the clock, with 0 on the number line coinciding with 0 on the clock face. Then the numbers : : : ; 3n; 2n; n; 0; n; 2n; 3n; : : : on the number line all overlay 0 on the clock face. The numbers : : : ; 3n C 1; 2n C 1; n C 1; 1; n C 1; 2n C 1; 3n C 1; : : : on the number line all overlay 1 on the clock face. In general, for 0  k 

n

1, the numbers : : : ; 3n C k; 2n C k; n C k; k; n C k; 2n C k; 3n C k; : : : on the number line all overlay k on the clock face.

When do two integers on the number line land on the same spot on the clock face? This happens precisely when the distance between the two numbers on the number line is some multiple of n, so that the interval between the two numbers on the number line wraps some integral number of times around the clock face. Since the distance between two numbers a and b on the number line is ja bj, this suggests the following definition:

Definition 1.7.1. Given integers a and b, and a natural number n, we say that “a is congruent to b modulo n” and we write a  b .mod n/ if a b is divisible by n.

The relation a  b .mod n/ has the following properties:

i

i

i

i



i

“bookmt” — 2006/8/8 — 12:58 — page 38 — #50

i

i

38

1. ALGEBRAIC THEMES Lemma 1.7.2.

(a) For all a 2 Z, a  a .mod n/.

(b) For all a; b 2 Z, a  b .mod n/ if, and only if, b  a .mod n/.

(c) For all a; b; c 2 Z, if a  b .mod n/ and b  c .mod n/, then a  c .mod n/.

Proof. For (a), a a D 0 is divisible by n. For (b), a b is divisible by n if, and only if, b a is divisible by n. Finally, if a b and b c are both divisible by n, then also a c D .a b/ C .b c/ is divisible by n.

n

For each integer a, write Œa D fb 2 Z W a  b .mod n/g D fa C k n W k 2 Zg:

Note that this is just the set of all integer points that land at the same place as a when the number line is wrapped around the clock face. The set Œa is called the residue class or congruence class of a modulo n.

Also denote by remn.a/ the unique number r such that 0  r