For example, if a = 28, b = 15 , then gcd(28,15) = 1 = 28(7)+15(?13) ; hence, s

Question

For example, if a = 28, b = 15 , then gcd(28,15) = 1 = 28(7)+15(?13) ; hence, s = 7and t = ?13 are

integers that the theorem guarantees to exist. The problem how to find them. Here is a method that is

based on the Euclidean Algorithm:

Step 1: Form the matrix

Step 2: Since 28 div15 = 1, subtract the second row from the first row:

Step 3: Since 15 div13 = 1, subtract the first row from the second row:

Step 4: Since 13 div 2 = 6 , subtract 6 times the second row from the first row:

Step 5: Since 2 div1 = 2 , subtract 2 times the first row from the second row:

At this point we are done because the second row has a zero in the third column. The desired

values are in the first row s = 7, t = ?13 , and d = 1. In fact, all possible values of s and t can

also be found! 28s +15t = 1 = gcd(a,b) if and only if s = 7 ?15k and t = ?13+ 28k .

In general, you need to repeat steps similar to steps 2 - 5 until a zero appears in the third column as in

step 5. If the zero is in the first row, then the second row contains the values s, t and d; otherwise, the

these values are in the first row.

Explanation / Answer

#include /*Takes a, b as input.Returns gcd(a, b).Updates x, y via pointer reference.*/int Extended_Euclid(int A, int B, int *X, int *Y){ int x, y, u, v, m, n, a, b, q, r; /* B = A(0) + B(1) */ x = 0; y = 1; /* A = A(1) + B(0) */ u = 1; v = 0; for (a = A, b = B; 0 != a; b = a, a = r, x = u, y = v, u = m, v = n) { /* b = aq + r and 0

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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