How many pairs of positive integers are there such that and have no common factors greater than and:
is an integer?
- A)
- B)
- C)
- D)
- E)
Answer
A
Key insight
Clearing denominators to 9ab | 9a^2 + 14b^2 and using gcd(a,b) = 1 forces a | 14 and b | 9, and the factor 9 forces 3 | b.
Solution
Combine the fractions:
This is an integer exactly when . Extract consequences using .
Bound . From we get , and since is coprime to , . Also gives , so . Thus .
Bound . From and coprimality, , so .
Case . The condition becomes , so , which needs . No divisor of works.
Case . The condition becomes , i.e. . Each is coprime to and divides , and , so all four work. Directly:
The pairs are : four in all.
The answer is .
Why this works
"Expression is an integer" becomes a divisibility statement once the fractions are combined, and coprimality converts into : a divisor coprime to one factor must divide the other. That squeezes an infinite search into a handful of candidates, which are then checked one by one. The extra factor of in the denominator is what kills and .
The trap
Only using b | 9 and a | 14 (twelve candidate pairs) without checking the full divisibility, or overlooking that 9 must divide 14b^2.
Common mistakes
- Only using b | 9 and a | 14 (twelve candidate pairs) without checking the full divisibility, or overlooking that 9 must divide 14b^2.
- Answering "infinitely many" because scaling preserves the expression, forgetting that the coprime condition removes those multiples.
Techniques
Organized listing / direct enumeration · Split into exhaustive cases and handle each