MATH135 Lecture Notes - Euclidean Algorithm, Calipers, Linear Combination
16 Oct 2011
School
Department
Course
Professor
40
MATH135 Full Course Notes
Verified Note
40 documents
Document Summary
Definition: let a,b,d if d|a and d|b, we say d is a common divider of a and b. Definition2: let a, b , not both 0. If d is the largest positive integer dividing both a and b, we say d is the greatest common divider of a and b, denoted by d=gcd(a,b). Ex: the common dividers of 45 and 75 are. 1, 3, 5 and 15. Dividers of 3 are 1, 3. All integers are dividers of 0, (since 0=0 x a, Thus their common dividers are 1, 3, and gcd(3,0)=3. In general, for with a 0, gcd(a,0) = a| To keep the above, we define gcd(0,0)=0, although 0 is not the largest common divider of 0 and 0. If a=b=0, then gcd(a,b) = 0 = gcd(5a+4b, a+b). Thus we can assume now that a,b are not both 0. Thus d is a common dividor of a and b. Let e be any common divider of a and b.
