COT 3100 Quiz #9: Euclid's Algorithm 3/23/05
COT 3100 Quiz #9: Euclid's Algorithm Solution 3/23/05
1) a) Using the Euclidean algorithm, find gcd(427, 154).
427 = 2(154) + 119 (1)
154 = 1(119) + 35 (2)
119 = 3(35) + 14 (3)
35 = 2(14) + 7 (4)
14 = 2(7), (5)
Thus, gcd(427, 154) = 7.
b) Using the Extended Euclidean Algorithm find all pairs of integers x and y that satisfy the equation 427x + 154y = gcd(427, 154).
35 - 2(14) = 7, (6) which is obtained by writing (4) backwards.
We know that 14 = 119 - 3(35) from (3), so now substitute for 14 into (6):
35 - 2(119 - 3(35)) = 7
35 - 2(119) + 6(35) = 7
7(35) - 2(119) = 7 (7)
We know that 35 = 154 - 119 from (2), so now substitute for 35 into (7):
7(154-119) - 2(119) = 7
7(154) - 7(119) - 2(119) = 7
7(154) - 9(119) = 7 (8)
We know that 119 = 427 - 2(154) from (1), so now substitute for 119 into (8):
7(154) - 9(427 - 2(154)) = 7
7(154) - 9(427) + 18(154) = 7
25(154) - 9(427) = 7
Thus, a solution is x= -9 and y=25. To find all solutions, consider the following equation:
427a + 154b = 0
61a + 22b = 0
61a = -22b. Since gcd(a,b)=1, the smallest solution is a=22, b=-61. It follows that the complete solution for x and y is
x = -9+22n,
y=25-61n, for all n(Z.
2) Write a recursive C function that computes the gcd of two given non-negative integers a and b. (Note: You are guaranteed that both a and b aren't 0, since gcd(0,0) isn't defined. Also, remember that you can NOT divide by 0!!!) The prototype is given to you below:
// Precondition: a and b are non-negative and at least one
// of them is not equal to 0.
int gcd(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
if (a%b == 0)
return b;
else
return gcd(a%b, b);
}
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.