The Euclidean Algorithm is used to produce a sequence X1 > X2 > X3 > X4 > X5 = 0 of positive integers where Xt = qt + 1Xt + 1 + Xt + 2, t = 1, 2, 3. The quotients are q2 = 3, q3 = 2, and q4 = 2. Which of the following is correct? Correct Answer gcd(X1, X2) = -2X1 + 7X2 Concept: The Euclidean Algorithm state that if a = bq + r where q and r are some integers then, the gcd of two numbers is given as gcd (a, b) = gcd (b, r) Calculation: By definition we have Xt = qt + 1Xt + 1 + Xt + 2, ⇒ X1 = q2X2 + X3 ⇒ X2 = q3X3 + X4 ⇒ X3 = q4X4 + X5 As we have, q2 = 3, q3 = 2, and q4 = 2, and X5 = 0 putting these values one by one. We get, ⇒ X3 = q4X4 + X5 = 2X4 + 0 = 2X4 ⇒ X2 = q3X3 + X4 = 2X3 + X4 = 2(2X4) + X4 = 5X4 ⇒ X1 = q2X2 + X3 = 3X2 + X3 = 3(5X4) + 2X4 = 17X4 Now, gcd is given as ⇒ gcd(X1, X2) = gcd(17X4, 5X4) = X4 ⇒ gcd(X1, X2) = X4 = -34X4 + 35X4 = -2(17X4) + 7(5X4) = -2X1 + 7X2 Hence, the correct option is gcd(X1, X2) = -2X1 + 7X2.