The Art and Craft of Problem Solving

44 CHAPTER 2 STRATEGIES FOR INVESTIGATING PROBLEMS

theory problems in this and the next chapter. First let 's introduce some extremely

useful and important notation.

Let m be a positive integer. If a - b is a multiple of m, we write

a =b (mod m)

(read "a is congruent to b modulo m"). For example,

10 =1 (mod 3), 17= 102 (modS), 2=- 1 (mod 3), 32 =0 (mod 8).

This notation, invented by Gauss, is very convenient. Here are several facts that you

should verify immediately:

• If you divide a by b and get a remainder of r, then a = r (mod b).

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

k such that a = b+mk.

• If a = b (mod m) and c = d (mod m), then a+c = b+d (mod m) and ac = bd

(mod m).

Example 2.3.4 Prove that if p is prime then, modulo p, every nonzero number has a

unique multiplicative inverse; i.e., if x is not a multiple of p then there is a unique y E

{ 1 , 2, 3, ... , p - 1 } such that xy = 1 (mod p). [For example, if p = 7, the multiplicative

inverses (mod 7) of 1 , 2,3,4,5,6 are 1,4,5,2, 3,6, respectively.]

Solution: Let x E {I, 2, 3, ... , p - I} be non-zero modulo p; i.e., x is not a mUltiple

of p. Now consider the (p -I) numbers

x, 2x, 3x, ... , (p - 1 )x.

The crux idea: we claim that these numbers are all distinct modulo p. We will show

this by contradiction. Assume, to the contrary, that they are not distinct. Then we must

have

ux = vx (mod p), (7)

for u, v E {I, 2, 3 , ... , p - I} with u I- v. But (7) implies that

ux - vx = (u-v)x=O (modp);

in other words, (u - v)x is a multiple of p. But x is not a multiple of p by hypothesis,

and the value of u - v is non-zero and at most p - 2 in absolute value (since the biggest

difference would occur if one of x, y were 1 and the other were p - 1). Thus u - v

cannot be a multiple of p, either. Since p is a prime it is impossible, then, for the

product (u - v)x to be a multiple of p. That is the contradiction we wanted: we have

proven that x, 2x, 3x, ... , (p - I)x are distinct modulo p.

Since those p - 1 distinct numbers are also non-zero modulo p (why?), exactly

one of them has to equal 1 modulo p. Hence there exists a unique y in the set

{^1 ,^2 ,3, ... ,p-l} such that.xy = 1 (modp). _