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: Understanding the Question:
We need to find the quotient \( q \) and remainder \( r \) for each pair of numbers \( a \) and \( b \) using the Euclidean division algorithm and match them with Column-II.

Step 2: Key Formula or Approach:
According to the Euclidean Division Lemma, for any two integers \( a \) and \( b \) (where \( b \neq 0 \)), there exist unique integers \( q \) and \( r \) such that:
\[ a = bq + r, \quad \text{where } 0 \le r < |b| \] Note that the remainder \( r \) must always be non-negative.

Step 3: Detailed Explanation:
Let us compute \( q \) and \( r \) for each pair:
- Pair (a): \( a = -112, b = -7 \)
We need: \( -112 = -7q + r \) with \( 0 \le r < 7 \).
Since \( -112 \) is exactly divisible by \( -7 \):
\[ -112 = -7(16) + 0 \implies q = 16, r = 0 \] This matches with (IV). Thus, a-IV.
- Pair (b): \( a = 118, b = -9 \)
We need: \( 118 = -9q + r \) with \( 0 \le r < 9 \).
Let's find the quotient:
\[ 118 = -9(-13) + 1 = 117 + 1 \implies q = -13, r = 1 \] Since \( r = 1 \) satisfies \( 0 \le 1 < 9 \), this is correct.
This matches with (I). Thus, b-I.
- Pair (c): \( a = -109, b = 6 \)
We need: \( -109 = 6q + r \) with \( 0 \le r < 6 \).
Since \( a \) is negative, we find the multiple of 6 just smaller than \( -109 \), which is \( -114 \):
\[ -109 = 6(-19) + 5 = -114 + 5 \implies q = -19, r = 5 \] Since \( r = 5 \) satisfies \( 0 \le 5 < 6 \), this is correct.
This matches with (III). Thus, c-III.
- Pair (d): \( a = 115, b = 8 \)
We need: \( 115 = 8q + r \) with \( 0 \le r < 8 \).
\[ 115 = 8(14) + 3 = 112 + 3 \implies q = 14, r = 3 \] Since \( r = 3 \) satisfies \( 0 \le 3 < 8 \), this is correct.
This matches with (II). Thus, d-II.
Combining these results: a-IV, b-I, c-III, d-II, which corresponds to Option (C).

Step 4: Final Answer:
(C) a-IV, b-I, c-III, d-II