Use the extended Euclidean algorithm to find the greatest common divisor of $8,406$ and $1,242$ and express it as a linear combination of $8,406$ and $1,242.$

Step $1$: Find

q$1$

and

r$1$

so that

$8,406=1,242$ q$1+$ r$1,$

where

$0<=$ r$1<1,242.$

Then

r$1=8,4061,242$ q$1=$

$.$

Step $2$: Find

q$2$

and

r$2$

so that

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

where

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

Then

r$2=1,242$

$$ 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 $(8406,1242)$

equals which of the following.

gcd $(8406,1242)=$ r$1$ r$2$ q$4$

gcd $(8406,1242)=$ r$2$ r$3$ q$4$

gcd $(8406,1242)=$ r$2$ r$4$ q$5$

gcd $(8406,1242)=$ r$3$ r$4$ q$5$

gcd $(8406,1242)=$ r$4$ r$5$ q$3$

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 $(8406,1242)=8,406$s $+1,242$t$,$

where

s $=$

and

t $=$

$.$