Class Notes (1,100,000)
CA (620,000)
UW (20,000)
MATH (2,000)
MATH135 (400)
Lecture 26

# MATH135 Lecture 26: Exercises - GCD

Department
Mathematics
Course Code
MATH135
Professor
Roxane Itier Itier
Lecture
26

This 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
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