Finding $d=\gcd(a,b)$; finding integers $m$ and $n$: $d=ma+nb$

5k Views Asked by At

Let $a=8316$ and $b=10920$

a) Find $d=\gcd(a,b)$. greatest common divisor of $a$ and $b$

b) Find integers $m$ and $n$ such that $d=ma+nb$

this is what i've tried so far. correct me if I'm wrong

8316= 8016*4 + 300

10920= 10800*300 + 120

300= 120*2 + 60

60=30*2

1

There are 1 best solutions below

0
On

The Extended Euclidean algorithm yields the coefficients and the g.c.d.:

enter image description here

Hence the g.c.d. is $84$, and $$84=-21\cdot 8316+16\cdot 10920$$