How to find an integer pair x and y after performing Eucilid algorithm?

Question

After performing a Euclid algorithm such as finding the greatest common divisor GCD(3745, 1172);

How can I find an X and Y for an equation like 3745x + 1172y = 5 ?

I'm quite confused at how to approach this question so would appreciate any assistance.

Answer 1

Hint: $$3745a+1172b=1 \implies 3745(ra)+1172(rb)=r.$$

Answer 2

$$ \gcd( 3745, 1172 ) = ??? $$

$$ \frac{ 3745 }{ 1172 } = 3 + \frac{ 229 }{ 1172 } $$ $$ \frac{ 1172 }{ 229 } = 5 + \frac{ 27 }{ 229 } $$ $$ \frac{ 229 }{ 27 } = 8 + \frac{ 13 }{ 27 } $$ $$ \frac{ 27 }{ 13 } = 2 + \frac{ 1 }{ 13 } $$ $$ \frac{ 13 }{ 1 } = 13 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 3 & & 5 & & 8 & & 2 & & 13 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 3 }{ 1 } & & \frac{ 16 }{ 5 } & & \frac{ 131 }{ 41 } & & \frac{ 278 }{ 87 } & & \frac{ 3745 }{ 1172 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 3 \\ \frac{ 3 }{ 1 } & \mbox{digit} & 5 \\ \frac{ 16 }{ 5 } & \mbox{digit} & 8 \\ \frac{ 131 }{ 41 } & \mbox{digit} & 2 \\ \frac{ 278 }{ 87 } & \mbox{digit} & 13 \\ \frac{ 3745 }{ 1172 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 3745 \cdot 87 - 1172 \cdot 278 = -1 $$

and then.....................