Question

Match the following-
tabularll Column-I & Column-II
(\(a, b\) as given in Euclidean Algorithm \(a = bq + r\)) & (Values of \(q\) and \(r\))
(a) \( a = -112, b = -7 \) & (I) \( q = -13, r = 1 \)
(b) \( a = 118, b = -9 \) & (II) \( q = 14, r = 3 \)
(c) \( a = -109, b = 6 \) & (III) \( q = -19, r = 5 \)
(d) \( a = 115, b = 8 \) & (IV) \( q = 16, r = 0 \)
tabular
Choose the correct answer from the options given below:

• A. a-III, b-I, c-IV, d-II
• B. a-III, b-II, c-IV, d-I
• C. a-IV, b-I, c-III, d-II
• D. a-IV, b-II, c-III, d-I

Hint:

Remember that the remainder \( r \) in Euclidean division is strictly non-negative (\( r \ge 0 \)). When dividing negative numbers, choose \( q \) such that the product \( bq \) is less than or equal to \( a \), so that \( r \) remains positive.

Answer 1

The Correct Option is C

Step 1: State the division rule.
For $a=bq+r$ we need the remainder to satisfy $0\le r<|b|$, which fixes $q$ and $r$ uniquely.
Step 2: Pair (a) $a=-112,\,b=-7$.
$-112=-7(16)+0$, so $q=16,\,r=0$, matching (IV). So a-IV.
Step 3: Pair (b) $a=118,\,b=-9$.
$118=-9(-13)+1$, so $q=-13,\,r=1$, matching (I). So b-I.
Step 4: Pair (c) $a=-109,\,b=6$.
$-109=6(-19)+5$ since $6\times(-19)=-114$, so $q=-19,\,r=5$, matching (III). So c-III.
Step 5: Pair (d) $a=115,\,b=8$.
$115=8(14)+3$, so $q=14,\,r=3$, matching (II). So d-II.
Step 6: Assemble the matches.
a-IV, b-I, c-III, d-II.
\[ \boxed{\text{a-IV, b-I, c-III, d-II}} \]