Match List I with List II and select the correct answer: List I ($a, b$ as given in Euclidean algorithm $a = bq + r$) A. $a = -112, b = -7$ B. $a = 118, b = -9$ C. $a = -109, b = 6$ D. $a = 115, b = 8$ List II (Values of $q$ and $r$) 1. $q = -13, r = 1$ 2. $q = 14, r = 3$ 3. $q = -19, r = 5$ 4. $q = 16, r = 0$

### Concept & Formula The Euclidean division algorithm states that for any two integers $a$ and $b$ (where $b \neq 0$), there exist unique integers $q$ (quotient) and $r$ (remainder) such that: $$a = bq + r$$ **Crucial Constraint:** The remainder $r$ must always be non-negative and strictly less than the absolute value of the divisor. Mathematically: $0 \le r < |b|$. ### Step-by-Step Solution Let's evaluate each pair to find valid $q$ and $r$ values that satisfy $0 \le r < |b|$. * **Evaluate A:** $a = -112, b = -7$ $-112 \div -7 = 16$ exactly. Equation: $-112 = -7(16) + 0$. Here, $q = 16, r = 0$. This maps **A to 4**. * **Evaluate D (Easiest positive numbers next):** $a = 115, b = 8$ $115 \div 8 = 14$ with a remainder. Equation: $115 = 8(14) + r \implies 115 = 112 + 3$. Here, $q = 14, r = 3$. This maps **D to 2**. * **Evaluate B:** $a = 118, b = -9$ We need a quotient $q$ such that $-9 \times q$ is just below $118$. Try $q = -13$: $-9(-13) = 117$. Equation: $118 = 117 + r \implies r = 1$. (Since $0 \le 1 < |-9|$, this is valid). Here, $q = -13, r = 1$. This maps **B to 1**. * **Evaluate C:** $a = -109, b = 6$ We need a quotient $q$ such that $6 \times q \le -109$. Try $q = -18$: $6(-18) = -108 \implies r = -1$ (Invalid, remainder must be positive). Try $q = -19$: $6(-19) = -114$. Equation: $-109 = -114 + r \implies r = 5$. (Since $0 \le 5 < |6|$, this is valid). Here, $q = -19, r = 5$. This maps **C to 3**. The final matching sequence is A-4, B-1, C-3, D-2. ### Exam Strategy & Shortcut Use Option Elimination. Start with the easiest calculations: 1. $D (115, 8)$ is basic division. $115 = 8 \times 14 + 3$. D matches 2. Looking at the options, only (a) and (c) end in 2. 2. Next easiest is $A (-112, -7)$. $-112 = -7 \times 16 + 0$. A matches 4. Looking at the remaining options (a) and (c), only option (c) starts with 4. You can select (c) immediately without calculating B or C. ### Common Pitfall When dealing with negative dividends like C ($-109$ divided by $6$), students often mistakenly choose quotient $-18$ and remainder $-1$. While $-108 - 1 = -109$, it violates the strict rule that remainders in Euclidean algorithms cannot be negative. You must push the quotient one integer further down (to $-19$) to force a positive remainder. ### Final Answer **Therefore, the correct answer is 4 1 3 2.**