The Art and Craft of Problem Solving

230 CHAPTER 7 NUMBER THEORY

7.2 Congruence

Congruence notation was introduced on page 44. Recall that if a - b is a mUltiple of

m, we write a == b (mod m) (read "a is congruent to b modulo m").

7.2. 1 Here are several facts that you should verify immediately.

(a) If you divide a by b and get a remainder of r, that is equivalent to saying that

a==r (mod b).

(b) There are only m "different" integers modulo m, since there are only m different

remainders (^0) , 1,2, ... , m -1. We call these m numbers the integers modulo m
or Zm. For example, in Z6 we have 5 + 5 = 4, 25 = 2, etc. Another term that is

used is residue modulo m. For example, one might say that 7 and 3 are different

residues modulo 5, but equal residues modulo 4.

(c) The statement a == b (mod m) is equivalent to saying that there exists an integer

k such that a = b+mk.

(d) Ifa==b (modm)andc==d (modm),thena+c==b+d (modm)andac==bd

(mod m).

The last statement is especially useful. For example, suppose we wanted to find

the remainder when we divide 2 \^000 by 17. Note that 24 = 16 == -1 (mod 17). Thus

2 \^000 = (2^4 )^250 == ( - 1 )^250 == 1, so the remainder is 1.

7.2.2 Two more examples of this method yield the following well-known divi sibility

rules. Prove them and learn them!

(a) If a number is written in base 10 , then it is congruent to the sum of its digits

modulo 9 and modulo 3.

(b) If a number is written in base 10 , then it is congruent modulo 11 to the units digit

• tens digit + hundreds digit -thousands digit, etc.

Viewing a problem modulo m for a suitably chosen m is a wonderful simplification

tactic because it reduces the infinite universe of integers to the finite world of Zm. You

have encountered this idea before with parity (page 94), which is just the case m = 2,

as well as other values of m (page 100). Often (but not always) we turn to prime values

of m, since primes are simpler, more "fundamental" objects that are generally easier to

understand. In general,

When beginning a number theory investigation, assume that the vari­

ables are prime or at least relatively prime. Often the general case

fo llows from the prime case, with just a few "technical" details.

Example 7.2.3 Fermat's Last Theorem. Let n 2: 3. Prove that the equation

has no non-zero integer solutions.