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

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

Thusrcan only be 0 or 1. Thus every integer is of the form 2kor 2k+1. The integers of the form 2kare

calledevenintegers, while those of the form 2k+1 are calledoddintegers. (Usually, an even integer is

defined as an integer divisible by 2, and all other integers are said to be odd. Thus the division algorithm

proves that every odd integer has the form 2k+1.)

11.5Divisibility, Primes

Letaandbbe integers witha=0. Supposeac=bfor some integerc. We then say thatadividesborbis

divisible bya, and we denote this by writing

a|b

We also say thatbis amultipleofaor thatais afactorordivisorofb.Ifadoes not divideb, we will writea |b.

EXAMPLE 11.3

(a) Clearly, 3|6 since 3· 2 =6, and− 4 |28 since(− 4 )(− 7 )=28.

(b)Thedivisors of 4 are±1,±2,±4 and the divisors of 9 are±1,±3,±9.

(c) Ifa=0, thena|0 sincea· 0 =0.

(d) Every integerais divisible by±1 and±a. These are sometimes called thetrivial divisorsofa. The basic

properties of divisibility is stated in the next theorem (proved in Problem 11.24).

Theorem 11.9: Supposea, b, care integers.

(i) Ifa|bandb|c, thena|c.

(ii) Ifa|bthen, for any integerx, a|bx.

(iii) Ifa|banda|c, thena|(b+c)anda|(b−c).

(iv) Ifa|bandb=0,thena=±bor|a|<|b|.

(v) Ifa|bandb|a, then|a|=|b|, i.e.,a=±b.

(vi) Ifa|1 , thena=± 1

Putting (ii) and (iii) together, we obtain the following important result.

Corollary 11.10: Supposea|banda|c. Then, for any integersxandy, a|(bx+cy). The expressionbx+cy

will be called alinear combinationofbandc.

Primes

A positive integerp>1 is called aprime numberor aprimeif its only divisors are±1 and±p, that is, if
ponly has trivial divisors. Ifn>1 is not prime, thennis said to becomposite. We note (Problem 11.13) that if
n>1 is composite thenn=abwhere 1<a,b<n.