← MATH 01352 · Theory of Numbers
MATH 01352 · Divisibility & primes
gcd / Euclidean algorithm
Definition
gcd(a,b) is the largest positive integer dividing both. Euclidean algorithm: gcd(a,b)=gcd(b,a mod b). Extended form finds Bézout coefficients: gcd=as+bt.
Read this
If gcd(a,b)=1, a and b are coprime — inverses mod n exist when gcd(a,n)=1.
Back-substitution or extended EA produces s,t.
gcd divides any integer linear combination of a and b.
Drill with flashcards
Flip through these until you can say the answer before revealing it.
Flashcards · 1 / 3
Click the card to flip
Try this
Attempt each problem first, then open the worked solution.
1.Run EA on (252,198) and find Bézout coefficients.