Class Notes (1,100,000)

CA (620,000)

UW (20,000)

MATH (2,000)

MATH135 (400)

Roxane Itier Itier (10)

Lecture 26

School

University of WaterlooDepartment

MathematicsCourse Code

MATH135Professor

Roxane Itier ItierLecture

26This

**preview**shows pages 1-2. to view the full**6 pages of the document.**MATH 135, Winter 2015

Exercises: Greatest Common Divisors

Part 1

1. For each pair of integers aand bgiven below, compute dgcdpa, bqas well as integers xand

ysuch that ax by d.

(a) a2109, b361.

(b) a76, b123.

(c) a 247, b117.

2. Let xand ybe integers such that gcdpx, yq 6. Show that either 4 -xor 4 -y.

3. Let a, b PZ. Prove that if cPZis any common divisor of aand b, then c|gcdpa, bq.

4. True or False? “For any a, b PZ, if a-b, then gcdpa, bq 1.” (Of course, justify!)

5. True or False? “For any a, b PZ, if gcdpa, bq 1, then a-b.”

6. True or False? “For any a, b, c PZ, if a|bc and a-b, then a|c.”

7. Let a, b, c PN.

(a) If a|b, prove that gcdpa, cq ¤ gcdpb, cq.

(b) If a¤b, is it true that gcdpa, cq ¤ gcdpb, cq?

8. Let a, b, c, d PZ. Suppose that d|ab,d|ac and gcdpb, cq 1. Prove that d|a.

9. Suppose that a, b, c, d PZsatisfy gcdpa, bq 1, c|aand d|b. Prove that gcdpc, dq 1.

10. (a) For any integer n, prove that 8n3 and 5n2 are coprime.

(b) Find a simple formula that computes gcdp8n3,5n2qfor any nPZ.

(c) Prove that for any nPZ, gcdp21n5,6n2qcan be either 1, 2 or 4. More precisely,

show that gcdp21n5,6n2q gcdpn1,4q.

11. Suppose that a, b PZare coprime. Prove that gcdpab, a bq 1 or 2.

1

Only pages 1-2 are available for preview. Some parts have been intentionally blurred.

12. Prove the following generalization of Coprimeness And Divisibility (CAD). Suppose a, b PZ

with gcdpa, bq 0. Then for any cPZ,

a|bc if and only if a

gcdpa, bq|c.

(Suggestion: The “if” (ð) direction is easy. For the “only if” (ñ) direction, use both DBGCD

and CAD.)

13. Given positive integers aand b, let dgcdpa, bq. Deﬁne

`ab

gcdpa, bqab

d.

Verify that `PN. If either a0 or b0, we set `0. Prove that `satisﬁes the following

properties:

(i) a|`and b|`; and

(ii) for all mPZ, if a|mand b|m, then `|m.

The number `is called the least common multiple of aand band is denoted by lcmpa, bq.

14. Given two integers a, b ¡1, let `lcmpa, bq. Prove that

01

a1

b1

`1.

15. Let a, b PZ. Prove that aand bare coprime if and only if they have no common prime

factors.

Remark. An equivalent version of this result states that gcdpa, bq ¡ 1 if and only if there

exists a prime psuch that p|aand p|b. This can be useful when dealing with GCDs.

16. Let a, b PZ. Use Exercise 15 to prove that if gcdpa, bq 1, then gcdpam, bnq 1 for all

m, n PN.

17. (a) Let a, b, c PZ. Prove that if gcdpa, bq 1, then gcdpa, bcq gcdpa, cq. Deduce that if

gcdpa, bq gcdpa, cq 1, then gcdpa, bcq 1.

(b) Generalize (a) as follows. Prove that for any nPNand a, b1, b2, . . . , bnPZ, if gcdpa, biq

1 for every 1 ¤i¤n, then gcdpa, b1 bncq gcdpa, cqfor all cPZ. In particular,

deduce that if gcdpa, biq 1 for every i, then gcdpa, b1 bnq 1.

(c) Use (b) to solve Exercise 16 (without using Exercise 15).

2

###### You're Reading a Preview

Unlock to view full version