This question was previously asked in

DSSSB TGT Maths Female Subject Concerned - 18 Nov 2018 Shift 3

Option 4 : 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,

⇒ X_{1} = q_{2}X_{2 }+ X_{3}

⇒ X_{2} = q_{3}X_{3} + X_{4}

⇒ X_{3} = q_{4}X_{4} + X_{5}

As we have,

q2 = 3, q3 = 2, and q4 = 2, and X_{5} = 0 putting these values one by one.

We get,

⇒ X3 = q4X4 + X_{5} = 2X_{4} + 0 = 2X4

⇒ X2 = q3X3 + X_{4} = 2X_{3} + X_{4} = 2(2X_{4}) + X_{4} = 5X_{4}

⇒ X1 = q2X2 + X_{3} = 3X_{2} + X_{3} = 3(5X_{4}) + 2X_{4} = 17X_{4}

Now, gcd is given as

⇒ gcd(X_{1}, X_{2}) = gcd(17X_{4}, 5X_{4}) = X_{4}

⇒ gcd(X1, X2) = X_{4} = -34X_{4} + 35X_{4} = -2(17X_{4}) + 7(5X_{4}) = -2X_{1} + 7X_{2}

**Hence, the correct option is gcd(X1, X2) = -2X1 + 7X2.**