OA. free
Free
Qualcomm Digital Electronics Digital Electronics Medium

When two numbers (not coprime) and their gcd are added, it results in 187.

Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.

When two numbers (not coprime) and their gcd are added, it results in 187. How many such pairs of two numbers are possible?

Choose one option.
Show answer & explanation
Answer: D. 6

Let the two numbers be a and b with gcd(a,b) = g. We can write a = gm and b = gn where gcd(m,n) = 1. The condition gives: gm + gn + g = 187, so g(m + n + 1) = 187. Since 187 = 11 × 17, the divisors are {1, 11, 17, 187}. For each divisor g, we need m + n + 1 = 187/g with gcd(m,n) = 1 and m,n ≥ 1 (not coprime means both > 1 or sharing factor, but since gcd(m,n) = 1 and a,b are not coprime, we need m,n > 1). Valid pairs exist for g ∈ {11, 17}, yielding 6 total pairs.

Step-by-step Derivation:
Let a = gm, b = gn where g = gcd(a,b) and gcd(m,n) = 1.
Given: a + b + g = 187
Substituting: gm + gn + g = 187
Factoring: g(m + n + 1) = 187 = 11 × 17

Divisors of 187: {1, 11, 17, 187}

Case 1: g = 1 → m + n + 1 = 187 → m + n = 186. But a,b not coprime means gcd(a,b) ≠ 1, so g > 1. Invalid.

Case 2: g = 11 → m + n + 1 = 17 → m + n = 16. Need gcd(m,n) = 1, m,n ≥ 1.
Valid coprime pairs (m,n) with m + n = 16: (1,15), (3,13), (5,11), (7,9), (9,7), (11,5), (13,3), (15,1).
All 8 pairs have gcd = 1. Count = 8 ordered pairs (or 4 unordered).

Case 3: g = 17 → m + n + 1 = 11 → m + n = 10. Need gcd(m,n) = 1, m,n ≥ 1.
Valid coprime pairs (m,n) with m + n = 10: (1,9), (3,7), (7,3), (9,1).
All 4 pairs have gcd = 1. Count = 4 ordered pairs (or 2 unordered).

Case 4: g = 187 → m + n + 1 = 1 → m + n = 0. Invalid (m,n must be positive).

Assuming the question asks for ordered pairs: 8 + 4 = 12. But if unordered distinct pairs: 4 + 2 = 6.