1.2 Properties of Integers

10

CHAPTER 1. PRELIMINARIES

1.2

Properties of Integers

1.2.1

The Well Ordering Principle and the Division Algorithm

We now focus on a special set, the integers, denoted Z, as this set plays an

important role in abstract algebra. We begin with an important result we will

use often, the Well Ordering Principle. We will state it as an axiom, as it cannot

be proven using the usual properties of arithmetic.

Axiom 23 (Well Ordering Principle) Every nonempty set of positive integers contains a smallest element.

Example 24 S = f1; 3; 5; 7; 9g is a set of positive integers. Its smallest element

is 1.

Can we say the same about sets of positive real numbers?

Next, we look at the concept of divisibility, an important concept in number

theory.

De¡­nition 25 A nonzero integer t is a divisor of an integer s and we write

t j s (read " t divides s") if there exists an integer k such that s = kt. In this

case, we also say that s is a multiple of t. When t is not a divisor of s, we

write t - s.

De¡­nition 26 A prime is a positive integer greater than 1 whose only positive

divisors are 1 and itself.

Example 27 The divisors of 8 are

1,

2,

Example 28 The divisors of 7 are

1 and

4 and

8.

7. So, 7 is prime.

Example 29 What are the divisors of 0?

A fundamental property of the integers is the division algorithm. Its proof

involves the Well Ordering Principle. We now state and prove this result which

we will use often.

Theorem 30 (Division Algorithm) Let a and b be integers with b > 0.

Then, there exists unique integers q and r with the property that

a = bq + r

(1.1)

where 0 r < b

Proof. First we prove existence, then uniqueness.

Existence. With a and b as given, consider the set S = fa

Either 0 2 S or 0 2

= S.

bk j k is an integer and a

bk

0g.

1.2. PROPERTIES OF INTEGERS

11

Case 1 0 2 S, then there exists an integer k, call it q, such that a qb = 0

a

or a = qb. hence, we have existence with q = and r = 0.

b

Case 2 0 2

= S. We want to use the Well Ordering Principle. For this, we

have to show S is a nonempty set of positive integers. Since a, b and

k are integers, a bk is also an integer. Since a bk 0 and 0 2

= S,

we know that a bk > 0. We need to show S 6= ?. If a > 0 then

a 0 b = a > 0 2 S. If a < 0, then a b (2a) = a (1 2b) > 0 2 S.

By the Well Ordering Principle, S has a smallest member. Call q

the value of k for which a bk is the smallest member of S and

r = a bq. Then, r 0 and a = bq + r. We still need to prove r < b.

We do a proof by contradiction. Suppose r b. Then a b (q + 1) =

a bq b = r b 0. However, a b (q + 1) < a bq and a bq is

the smallest member of S, so we can¡¯t have a b (q + 1) 0. Thus

r < b.

Uniqueness. We assume there are at least two integers satisfying the condition and we show they are equal. Suppose that there exist integers q and

q 0 and r and r0 such that a = bq + r and a = bq 0 + r0 with 0

r < b

and 0 r0 < b. Without loss of generality, we may assume r r0 . Then,

bq + r = bq0 + r0 or b (q 0 q) = r0 r. so b j r0 r but 0 r0 r < r0 < b.

So, we must have r0 r = 0 which also implies q 0 q = 0.

Remark 31 This is the division you have been doing since you were little. r is

the remainder. If r = 0, then b j a.

Example 32 For a = 20 and b = 3, the algorithm gives 20 = 3 6 + 2.

1.2.2

Greatest Common Divisor, Relatively Prime Integers

De¡­nition 33 (Greatest Common Divisor) Let m and n be two nonzero

integers. The greatest common divisor of m and n, denoted gcd (m; n), is

de¡­ned to be the largest of all common divisors of m and n.

De¡­nition 34 (Relatively Prime) Two nonzero integers m and n are said

to be relatively prime if gcd (m; n) = 1.

There are di¡èerent techniques to ¡­nd gcd (a; b). We illustrate one known as

the Euclidean algorithm. We begin with some remarks. Suppose we are given

integers a and b, assume a

b. Then, by the division algorithm, there exists

unique integers q1 and r1 , 0 r1 < b such that a = bq1 +r1 . Any integer dividing

a and b will also divide b and r1 (see problems) hence gcd (a; b) = gcd (b; r1 ).

We repeat the process with b and r1 . There exists unique integers q2 and r2 ,

0 r2 < r1 such that b = r1 q2 + r2 . As before, gcd (b; r1 ) = gcd (r1 ; r2 ). We

12

CHAPTER 1. PRELIMINARIES

repeat the process with r1 and r2 to obtain unique integers q3 and r3 , 0 r3 < r2

such that r1 = r2 q3 + r3 . As before gcd (r1 ; r2 ) = gcd (r2 ; r3 ). Continuing this

way, we obtain a sequence of remainders r1 > r2 > r3 ::: where each ri 0. By

the well ordering principle, this process has to stop and some ri must eventually

be 0. We have

gcd (a; b) = gcd (b; r1 ) = gcd (r1 ; r2 ) = ::: = gcd (ri ; 0) = ri

See the problems for the last equality. Thus, gcd (a; b) is the last nonzero remainder arising from our repeated division. We illustrate this with an example.

Example 35 Let¡¯s ¡­nd gcd (100; 64).

100

=

64 1 + 36

64

=

36 1 + 28

36

=

28 1 + 8

28

=

8 3+4

8

=

4 2+0

Thus gcd (100; 64) = 4.

Remark 36 If a number is written as a product of prime factors, then ¡­nding

the greatest common divisor is simply a matter of gathering the common prime

factors which are common to both. More speci¡­cally, if a = ph1 1 ph2 2 :::phnn and

b = pk11 pk22 :::pknn where pi are primes, with the understanding that some of the

ki or hi might be 0 (if the corresponding prime is not present) and if we de¡­ne

si = min (hi ; ki ) for each i = 1::n, then

gcd (a; b) = ps11 ps22 :::psnn

Example 37 Find gcd 23 32 5 74 ; 2 52 7

gcd 23 32 5 74 ; 2 52 7

=

2 5 7

=

70

Theorem 38 For any nonzero integers a and b, there exists integers s and t

such that

gcd (a; b) = as + bt

Moreover, gcd (a; b) is the smallest positive integer of the form as + bt.

Proof. There are di¡è erent ways to prove the existence part. We outline them

here.

Method 1: Here, we only show that gcd (a; b) = as + bt. We use the Euclidean

algorithm developed above. So, this is a constructive proof. It will show

1.2. PROPERTIES OF INTEGERS

13

us how to ¡­nd s and t. Let us assume that the Euclidean algorithm gave

us the following:

a

= bq1 + r1

b

= r1 q2 + r2

r1

= r2 q3 + r3

..

.

ri

3

= ri

2 qi 1

+ ri

ri

2

= ri

1 qi

ri

1

= ri qi+1 + 0

1

+ ri

Thus gcd (a; b) = ri . But using ri 2 = ri 1 qi + ri , we can write ri =

ri 2 ri 1 qi thus writing ri as a linear combination of ri 1 and ri 2 .Using

the previous equation, we can write ri 1 = ri 3 ri 2 qi 1 thus we can

express ri as a linear combination of ri 2 and ri 3 . Using all the equations

in the Euclidean algorithm in reverse order, we can express ri as a linear

combination of a and b.

Method 2: This proof involves the division algorithm and the Well Ordering

Principle. It is similar in some ways to the proof of the division algorithm.

Here, we will prove everything stated in the theorem. But this proof is not

constructive, it does not tell us how to ¡­nd s and t. Consider the set

S = fam + bn j am + bn > 0 and m and n are integersg. Since a, b, m,

n are all integers, am+bn is an integer. So, S is a set of positive integers.

It is not empty because if am + bn < 0 then a ( m) + b ( n) > 0. Thus,

by the Well Ordering Principle, S has a smallest member, say d = as + bt.

We now prove that d = gcd (a; b). For this, we ¡­rst prove that d is a

divisor of both a and b and then that it is in fact, the largest common

divisor.

d is a divisor of both a and b. First, we establish d divides a.

Using the division algorithm, we can write a = dq + r with 0 r < d.

If we had r > 0, then

r

=

a

dq

=

a

(as + bt) q

=

a

asq

=

a (1

btq

sq) + b ( tq)

Thus we would have a (1 sq) + b ( tq) 2 S contradicting d is the

smallest member of S. Thus r = 0 hence a = dq or d j a. We can

carry a similar argument for d j b. Hence, d is a common divisor to

both a and b.

d is the largest common divisor to both a and b. Suppose d0 is

another common divisor to both a and b that is a = d0 h and b = d0 k.

14

CHAPTER 1. PRELIMINARIES

Then, d = as + bt = d0 hs + d0 kt = d0 (hs + kt) so d0 is a divisor of d,

hence d > d0 . Thus d is the greatest common divisor.

There is an important corollary of this theorem, which we will often use.

Remark 39 The proof shown in method 1: also gives a way to ¡­nd what that

combination is.

Example 40 Find s and t such that gcd (100; 64) = 100s + 64t.

Recall from above that gcd (100; 64) = 4. Using our computations above, we

have

4

=

28

8 3

=

28

3 (36

=

4 28

3 36

=

4 (64

36)

=

4 64

7 36

=

4 64

7 (100

28 1)

3 36

64)

7 100 + 11 64

Corollary 41 If a and b are relatively prime, then there exists integers s and

t such that as + bt = 1.

The next lemma is very important and often used.

Lemma 42 (Euclid¡¯s Lemma) Let a and b be integers. If p is prime and

p j ab then p j a or p j b.

Proof. It is enough to prove that if p - a then we must have p j b. So, suppose

p j ab and p - a. Then a and p are relatively prime and therefore there exist

integers s and t such that 1 = as + pt. Then, b = abs + bpt. Since p divides the

right hand side, it must also divide b.

p

This fact is used in particular when proving that p is irrational when p is

prime.

Prime numbers are extremely important when dealing with integers. They

are their building blocks, as the next result shows.

Theorem 43 (Fundamental Theorem of Arithmetic) Every integer greater

than 1 is either prime or a product of primes . This product is unique, except

for the order of the factors.

Proof. We will prove this result later in the chapter.

Example 44 66 = 2

3

Example 45 100 = 22 52

11

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download