Scribd
Upload
598 views2 pages

B) Using The Extended Euclidean Algorithm Find All Pairs of Integers X and y That Satisfy The Equation 427x + 154y GCD (427, 154)

This document contains the solution to a quiz on Euclid's algorithm and the extended Euclidean algorithm. [1] It uses Euclid's algorithm to find the greatest common divisor (gcd) of 427 and 154, which is 7. [2] It then uses the extended Euclidean algorithm to find all pairs of integers x and y that satisfy the equation 427x + 154y = 7, yielding the solution of x = -9 and y = 25. [3] It provides a recursive C function that implements Euclid's algorithm to compute the gcd of two non-negative integers.

Uploaded by

Emmaculate Ongum
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
598 views2 pages

B) Using The Extended Euclidean Algorithm Find All Pairs of Integers X and y That Satisfy The Equation 427x + 154y GCD (427, 154)

This document contains the solution to a quiz on Euclid's algorithm and the extended Euclidean algorithm. [1] It uses Euclid's algorithm to find the greatest common divisor (gcd) of 427 and 154, which is 7. [2] It then uses the extended Euclidean algorithm to find all pairs of integers x and y that satisfy the equation 427x + 154y = 7, yielding the solution of x = -9 and y = 25. [3] It provides a recursive C function that implements Euclid's algorithm to compute the gcd of two non-negative integers.

Uploaded by

Emmaculate Ongum
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOC, PDF, TXT or read online on Scribd
You are on page 1/ 2

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);

You might also like