Please show all steps. Thanks. In this problem we work out step-by-step the Exte

Question

Please show all steps. Thanks.

In this problem we work out step-by-step the Extended Euclidean Algorithm. Specifically, we will find two integers x, y so that 1285x + 630y = gcd(1285,630). To do this we first apply the Euclidean Algorithm to compute gdc(1285, 630) and then unwind the calculation to find x and y. By unwinding the second equation from the Euclidean algorithm 1285 = 630 times 2 + 25 630 = 25 times 25 + 5 we find that gcd(1285, 630) = 5 = 630 + 25 times (-25). (*) Note that 25 appears in the first equation. So let's solve for 25 and substitute that o (*). From the first equation, 25 = 1285 times + 630 times Substitute this o (*) and we find that gcd(1285, 630) = 5 = 1285 times + 630 times This completes the Extended Euclidean Algorithm in this case. In general it could take several steps to find the gcd, in which case you would need to unwind them in reversed order to find x and y.

Explanation / Answer

25= 1285*1+630*(-2)

5= 630 - 25*(1285-2*630)

= 51*630 + (-25)*1285

5 = 1285*(-25)+630*51

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.