MATH135 Lecture Notes - Lecture 5: Extended Euclidean Algorithm, Coprime Integers, Rational Number
14 May 2018
School
Department
Course
Professor
MATH 135 Fall 2015: Extra Practice Set 5
These problems are for extra practice and are not to be handed. Solutions will not be posted but, unlike
assignment problems, they may discussed in depth on Piazza.
•The warm-up exercises are intended to be fairly quick and easy to solve. If you are unsure about any
of them, then you should review your notes and possibly speak to an instructor before beginning the
corresponding assignment.
•The recommended problems supplement the practice gained by doing the corresponding assignment.
Some should be done as the material is learned and the rest can be left for exam preparation.
•A few more challenging extra problems are also included for students wishing to push themselves
even harder. Do not worry if you cannot solve these more difficult problems.
Warm-up Exercises
1. Disprove the following. Let a, b, c ∈Z. Then gcd(a, b) = gcd(a, c)·gcd(b, c).
2. Let a, b, c ∈Z. Consider the statement S: If gcd(a, b) = 1 and c|(a+b), then gcd(a, c) = 1. Fill in
the blanks to complete a proof of S.
(a) Since gcd(a, b) = 1, by there exist integers xand ysuch that ax +by = 1.
(b) Since c|(a+b), by there exists an integer ksuch that a+b=ck.
(c) Substituting a=ck −binto the first equation, we get 1 = (ck −b)x+by =b(−x+y) + c(kx).
(d) Since 1 is a common divisor of band cand −x+yand kx are integers, gcd(b, c) = 1 by
.
Recommended Problems
1. (a) Use the Extended Euclidean Algorithm to find three integers x, y and d= gcd(1112,768) such
that 1112x+ 768y=d.
(b) Determine integers sand tsuch that 768s−1112t= gcd(768,−1112).
2. Prove that for all a∈Z, gcd(9a+ 4,2a+ 1) = 1
3. Let gcd(x, y) = d. Express gcd(18x+ 3y, 3x) in terms of dand prove that you are correct.
4. Prove that if gcd(a, b) = 1, then gcd(2a+b, a + 2b)∈ {1,3}.
5. Prove that for every integer k, gcd(a, b)≤gcd(ak, b).
6. Given a rational number r, prove that there exist coprime integers pand q, with q6= 0, so that r=p
q.
7. Prove that: if a|cand b|cand gcd(a, b) = 1, then ab |c.
8. Let a, b, c ∈Z. Prove that if gcd(a, b) = 1 and c|a, then gcd(b, c) = 1.
9. Prove that if gcd(a, b) = 1, then gcd(am, bn) = 1 for all m, n ∈N. You may use the result of an
example in the notes.
40
MATH135 Full Course Notes
Verified Note
40 documents
Document Summary
Math 135 fall 2015: extra practice set 5. These problems are for extra practice and are not to be handed. Solutions will not be posted but, unlike assignment problems, they may discussed in depth on piazza: the warm-up exercises are intended to be fairly quick and easy to solve. If you are unsure about any of them, then you should review your notes and possibly speak to an instructor before beginning the corresponding assignment: the recommended problems supplement the practice gained by doing the corresponding assignment. Some should be done as the material is learned and the rest can be left for exam preparation: a few more challenging extra problems are also included for students wishing to push themselves even harder. Do not worry if you cannot solve these more di cult problems. Then gcd(a, b) = gcd(a, c) gcd(b, c): let a, b, c z.
