Use the extended Euclidean algorithm to find the greatest common divisor of $7,038$ and $720$ and express it as a linear combination of $7,038$ and $720.$

Step $1$: Find

q$1$

and

r$1$

so that

$7,038=720$ q$1+$ r$1,$

where

$0<=$ r$1<720.$

Then

r$1=7,038720$ q$1=$

$558$

Correct: Your answer is correct.

$.$

Step $2$: Find

q$2$

and

r$2$

so that

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

where

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

Then

r$2=720$

$558$

Correct: Your answer is correct.

$$ q$2=$

$162$

Correct: Your answer is correct.

$.$

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=$

$558$

Correct: Your answer is correct.

$$

$162$

Correct: Your answer is correct.

$$ q$3=$

$72$

Correct: Your answer is correct.

$.$

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=$

$162$

Correct: Your answer is correct.

$$

$72$

Correct: Your answer is correct.

$$ q$4=$

$18$

Correct: Your answer is correct.

$.$

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=$

$72$

Correct: Your answer is correct.

$$

$18$

Correct: Your answer is correct.

$$ q$5=$

$0$

Correct: Your answer is correct.

$.$

Step $6$: Conclude that

gcd $(7038,720)$

equals which of the following.

gcd $(7038,720)=$ r$1$ r$2$ q$4$

gcd $(7038,720)=$ r$3$ r$4$ q$5$

gcd $(7038,720)=$ r$2$ r$4$ q$5$

gcd $(7038,720)=$ r$2$ r$3$ q$4$

gcd $(7038,720)=$ r$4$ r$5$ q$3$

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 $(7038,720)=7,038$s $+720$t$,$

where

s $=$

$3$

Incorrect: Your answer is incorrect.

and

t $=$

$-32$

Incorrect: Your answer is incorrect.

$.$

Need Help?