0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

$$ \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.....................

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.