MATH135 Lecture Notes - Lecture 4: Euclidean Algorithm, Extended Euclidean Algorithm

66 views2 pages
leensy188 and 36637 others unlocked
MATH135 Full Course Notes
40
MATH135 Full Course Notes
Verified Note
40 documents

Document Summary

*gcd(a,b)=d>0 d|a and d|b c|a and c|b then c d. If we use this proposition (gcd with r) repeatedly we can compute large gcds. This process is known as the euclidean algorithm. But for large numbers, there can be mistakes. We can see how accurate our solution is by the following proposition theorem: If d is a positive common divisor of the integers a and b and integers x and y so that d=ax+by then gcd(a,b)=d. Proof: we want to show that d satisfies the definition of gcd(a,b). So from our hypothesis, we know that d|a and d|b (this is the first prof of the gcd definition) By dic, let x,yez and we can write c|(ax+by) By bd, we can write c d (second part of definition) The eea is an efficient way to compute the gcd(a,b) and x and y so that d=ax+by. We want the following to hold rn+1=0 rn=gcd(a,b) rn-2=qnrn-1+rn.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related textbook solutions

Related Questions