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

CHAP. 11] PROPERTIES OF THE INTEGERS 265 AppendixBshows that other mathematical structures have the above properties. One fundam ...

266 PROPERTIES OF THE INTEGERS [CHAP. 11 Absolute Value Theabsolute valueof an integera. written|a|, is formally defined by |a|= ...

CHAP. 11] PROPERTIES OF THE INTEGERS 267 SupposeP(k)is true. (This is called the inductive hypothesis.) Adding 2k+1 to both side ...

268 PROPERTIES OF THE INTEGERS [CHAP. 11 The numberqin the above theorem is called thequotient, andris called theremainder. We s ...

CHAP. 11] PROPERTIES OF THE INTEGERS 269 (c) Letb=2. Then any integeracan be written in the form a= 2 q+r where 0≤r< 2 Thusrc ...

270 PROPERTIES OF THE INTEGERS [CHAP. 11 EXAMPLE 11.4 (a) The integers 2 and 7 are primes, whereas 6= 2 ·3 and 15= 3 ·5 are comp ...

CHAP. 11] PROPERTIES OF THE INTEGERS 271 (c) For any primep, we have gcd(p, a)=por gcd(p, a)=1 according aspdoes or does not div ...

272 PROPERTIES OF THE INTEGERS [CHAP. 11 Fig. 11-3 Next we use equation (1) to replace 36 in (4) so we can write 12 as a linear ...

CHAP. 11] PROPERTIES OF THE INTEGERS 273 11.7Fundamental Theorem of Arithmetic This section discusses the Fundamental Theorem of ...

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, ...

CHAP. 11] PROPERTIES OF THE INTEGERS 275 Remark:Supposemis positive, andais any integer. By the Division Algorithm, there exist ...

276 PROPERTIES OF THE INTEGERS [CHAP. 11 EXAMPLE 11.12 Observe that 2≡8 (mod 6) and 5≡41 (mod 6). Then: (a) 2+ 5 ≡ 8 +41 (mod 6) ...

CHAP. 11] PROPERTIES OF THE INTEGERS 277 Cancellation Laws for Congruences Recall that the integers satisfy the following: Cance ...

278 PROPERTIES OF THE INTEGERS [CHAP. 11 EXAMPLE 11.14 (a) Consider the modulusm=15. There are eight integers between 1 and 15 w ...

CHAP. 11] PROPERTIES OF THE INTEGERS 279 (a) There are no solutions since 0, 1, 2, and 3 do not satisfy the equation. (b) There ...

280 PROPERTIES OF THE INTEGERS [CHAP. 11 EXAMPLE 11.17 Consider the following congruence equation: 81 ≡ 1 (mod 256) By observati ...

CHAP. 11] PROPERTIES OF THE INTEGERS 281 The complete story of the general case of (11.4) is contained in the following theorem ...

282 PROPERTIES OF THE INTEGERS [CHAP. 11 Proposition 11.30: Consider the system (11.8) of congruence equations. LetM=m 1 m 2 ... ...

CHAP. 11] PROPERTIES OF THE INTEGERS 283 We now substitute into the formula (11.9) to obtain the following solution of our origi ...

284 PROPERTIES OF THE INTEGERS [CHAP. 11 11.5. Prove Proposition 11.3: Supposea≤b, andcis any integer. Then: (i)a+c≤b+c, (ii)ac= ...