MATH135 Lecture 26: Exercises - GCD
SchoolUniversity of Waterloo
ProfessorRoxane Itier Itier
This preview shows pages 1-2. to view the full 6 pages of the document.
MATH 135, Winter 2015
Exercises: Greatest Common Divisors
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.
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
(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
Verify that `PN. If either a0 or b0, we set `0. Prove that `satisﬁes the following
(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
15. Let a, b PZ. Prove that aand bare coprime if and only if they have no common prime
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).
You're Reading a Preview
Unlock to view full version