Use Algorithm 2.3.7 to ?nd x, y ? Z such that 2261x + 1275y = 17. Algorithm 2.3.

Question

Use Algorithm 2.3.7 to ?nd x, y ? Z such that 2261x + 1275y = 17.


Algorithm 2.3.7 (Extended Euclidean Algorithm). Suppose a and b are
integers and let g = gcd(a, b). This algorithm ?nds g, x and y such that
ax + by = g. We describe only the steps when a > b ? 0, since one can
easily reduce to this case.
1. [Initialize] Set x = 1, y = 0, r = 0, s = 1.
2. [Finished?] If b = 0, set g = a and terminate.
3. [Quotient and Remainder] Use Algorithm 1.1.12 to write a = qb + c
with 0 ? c < b.
4. [Shift] Set (a, b, r, s, x, y) = (b, c, x ? qr,y ? qs,r,s) and go to Step 2.


Please explain all steps I'm have a heard time understand how to these. If you know a better way to slove please share :)

Explanation / Answer

Initially a = 2261, b = 1275, g = 17.

1. x = 1, y = 0, r = 0, s = 1

2. b is not 0, go to 3

3. 2261 = 1 * 1275 + 986: q = 1, c = 986

4. a get's the old b, b get's the old c:

a = 1275, b = 986, r = 1 - 1*0 = 1, s = 0-1*1 = -1, x = 0, y = 1

back to 2...

2. b is not 0, go to 3

3. 1275 = 1 * 986 + 289: q = 1, c = 289

4. a = 986, b = 289, r = 0-1 * 1 = -1, s = 1 - 1 * -1 = 2, x = 1, y = -1

2. b is not 0, go to 3

3. 986 = 3 * 289 + 119: q = 3, c = 119

4. a = 289, b = 119, r = 1 - 3*-1 = 4, s = -1 - 3*2 = -7, x = -1, y = 2

2. b is not 0, go to 3

3. 289 = 2 * 119 + 51: q = 2, c = 51

4. a = 119, b = 51, r = -1 -2*4=-9, s = 2 - 2 * -7 = 16, x = 4, y = -7

2. b is not 0, go to 3

3. 119 = 2*51 + 17: q = 2, c = 17

4. a = 51, b = 17, r = 4 - 2 * -9 = 22, s = -7 - 2 * 16 = -39, x = -9, y = 16

2. b is not 0, go to 3

3. 51 = 3*17 + 0: q = 3; c = 0 (next step will terminate!)

4. a = 17, b = 0, r = -9 - 3*22 = -75, s = 16 - 3*-39 = 133, x = 22, y = -39

2. b is 0, stop and set g = 17

Now we have that x = 22, y = -39 and...

2261*22 - 1275*39 is indeed 17, the greatest common divisor, g! Yay!

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

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