MACM 101 Lecture 26: Lecture 26 Part 1_ Common Divisors
39 views2 pages
21 Dec 2018
School
Department
Course
Professor
Document Summary
For integers a and b, a positive integer c is said to be a common divisor of a and b if c | a and c | b. Let a, b be integers such that a 0 or b 0. The greatest common divisor of a and b is denoted by gcd(a,b) For any positive integers a and b, there is a unique positive integer c such that c is the greatest common divisor of a and b. First try: take the largest common divisor, in the sense of usual order. Given a, b, let s = { as + bt | s,t z, as + bt > 0 }. Since s , it has a least element c. we show that c = gcd(a,b) We have c = ax + by for some integers x and y. If d | a and d | b, then d | ax + by = c.
Get access
Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers