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

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.

Hint: $$3745a+1172b=1 \implies 3745(ra)+1172(rb)=r.$$
$$\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$$