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
Over the common bottom 9ab: since a and b share no factor, b divides 9 and a divides 14, and the 9 forces b to be a multiple of 3.
Solution
Start with one example to see what can happen. With , :
a whole number. So solutions exist. Now find them all.
Step 1: one fraction. Over the common bottom ,
This is a whole number exactly when divides . In particular each of , and must divide the top.
Step 2: what can be?
- divides , so for to divide the top it must divide .
- shares no factor with , so it shares none with . So must divide : is , or .
- Also divides , so must divide . Since has no factor , must be a multiple of , so is a multiple of .
- That leaves or .
Step 3: what can be? In the same way, divides , so must divide . It shares no factor with , so divides : is , , or .
Step 4: test the pairs.
- : the expression is . For this is , , , . The part is never whole and the other part is, so none work.
- : the expression is .
| 1 | 2 | 7 | 14 | |
|---|---|---|---|---|
| value |
All four work.
So the pairs are , , , : four in all.
The answer is .
Why this works
"This is a whole number" becomes "the bottom divides the top" once the fractions are combined. The key fact is that if a number shares no factor with and divides , it must divide . That shrinks an endless search to a few candidates you can check by hand.
The trap
Stopping at 'b divides 9 and a divides 14' and counting all twelve pairs, without checking which ones actually give a whole number.
Concise 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 .
Review in the AoPS books
- Introduction to Number Theory, Chapter 7: Algebra With Integers
- Introduction to Number Theory, Chapter 3: Multiples and Divisors (§3.3, §3.4, §3.7)
- Introduction to Number Theory, Chapter 1: Integers: The Basics (§1.4, §1.5)
- Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)
Techniques
Organized listing / direct enumeration · Split into exhaustive cases and handle each