Use the extended Euclidean algorithm to find the greatest common divisor of $6,631$ and $988$ and express it as a linear combination of $6,631$ and $988.$

Step $1$: Find

q$1$

and

r$1$

so that

$6,631=988$ q$1+$ r$1,$

where

$0<=$ r$1<988.$

Then

r$1=6,631988$ q$1=$

$.$

Step $2$: Find

q$2$

and

r$2$

so that

$988=$ r$1$ q$2+$ r$2,$

where

$0<=$ r$2<$ r$1.$

Then

r$2=988$

$$ q$2=$

$.$

Step $3$: Find

q$3$

and

r$3$

so that

r$1=$ r$2$ q$3+$ r$3,$

where

$0<=$ r$3<$ r$2.$

Then

r$3=$

$$

$$ q$3=$

$.$

Step $4$: Find

q$4$

and

r$4$

so that

r$2=$ r$3$ q$4+$ r$4,$

where

$0<=$ r$4<$ r$3.$

Then

r$4=$

$$

$$ q$4=$

$.$

Step $5$: Find

q$5$

and

r$5$

so that

r$3=$ r$4$ q$5+$ r$5,$

where

$0<=$ r$5<$ r$4.$

Then

r$5=$

$$

$$ q$5=$

$.$

Step $6$: Conclude that

gcd $(6631,988)$

equals which of the following.

gcd $(6631,988)=$ r$1$ r$2$ q$4$

gcd $(6631,988)=$ r$4$ r$5$ q$3$

gcd $(6631,988)=$ r$2$ r$3$ q$4$

gcd $(6631,988)=$ r$2$ r$4$ q$5$

gcd $(6631,988)=$ r$3$ r$4$ q$5$

Correct: Your answer is correct.

Conclusion: Substitute numerical values backward through the preceding steps, simplifying the results for each step, until you have found numbers s and t so that

gcd $(6631,988)=6,631$s $+988$t$,$

where

s $=$

and

t $=$

$.$

Need Help?