Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

274 PROPERTIES OF THE INTEGERS [CHAP. 11

(b) Next we findm=lcm(a, b). Those primesp, which appear in eitheraorb, 2, 3, 5, 7, 11, 13, and 17, will

also appear inm, and the exponent ofpinmwill be the larger of its exponents inaandb. Thus

m=lcm(a, b)= 24 · 33 · 52 · 11 · 13 · 17

We are so used to using numbers as if the Fundamental Theorem of Arithmetic were true that it may seem as
if it needs no proof. It is a tribute to Euclid, who first proved the theorem, that he recognized that it does require
proof. We emphasize the nontriviality of the theorem by giving an example of a system of numbers which does
not satisfy this theorem.

EXAMPLE 11.10 LetFbe the set of positive integers of the form 3x+1. ThusFconsists of the numbers:

1 , 4 , 7 , 10 , 13 , 16 , 19 , 22 , ...

Note that the product of two numbers inFis again inFsince:

( 3 x+ 1 )( 3 y+ 1 )= 9 xy+ 3 x+ 3 y+ 1 = 3 ( 3 xy+x+y)+ 1

Our definition of primes makes perfectly good sense inF. Although 4= 2 ·2 , the number 2 is not inF. Thus 4
is prime inFsince 4 has no factors except 1 and 4. Similarly 10, 22, 25,... are primes inF. We list the first few
primes inF:
4 , 7 , 10 , 13 , 19 , 22 , 25 , ...

Note 100 = 3 ( 33 )+1 belongs toF. However, 100 has two essentially different factorizations into primes ofF;
namely,
100 = 4 ·25 and 100 = 10 · 10

Thus there is no unique factorization into primes inF.

11.8Congruence Relation

Letmbe a positive integer. We say thataiscongruenttobmodulom. written

a≡b(modulom) or simply a≡b(modm)

ifmdivides the differencea−b. The integermis called themodulus. The negation ofa≡b(modm) is written
a≡b(modm). For example:

(i) 87≡23 (mod 4) since 4 divides 87− 23 =64.

(ii) 67≡1 (mod 6) since 6 divides 67− 1 =66.

(iii) 72≡−5 (mod 7) since 7 divides 72−(− 5 )=77.

(iv) 27≡8 (mod 9) since 9 does not divide 27− 8 =19.

Ourfirsttheorem (proved in Problem 11.34) states that congruence modulomis an equivalence relation.

Theorem 11.21: Letmbe a positive integer. Then:

(i) For any integera, we havea≡a(modm).

(ii) Ifa≡b(modm), thenb≡a(modm).

(iii) Ifa≡b(modm) andb≡c(modm), thena≡c(modm).