2007 AMC 10B Problem 25

P21-25~8 minPrint

Diophantine Equations Divisibility & Factors GCD & LCM Organized listing / direct enumeration Split into exhaustive cases and handle each

How many pairs of positive integers $(a,b)$ are there such that $a$ and $b$ have no common factors greater than $1$ and:

$\frac{a}{b} + \frac{14b}{9a}$

is an integer?

Show solution without answering

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 = 1$ , $b = 3$ :
$\frac13 + \frac{42}{9} = \frac13 + \frac{14}{3} = \frac{15}{3} = 5,$
a whole number. So solutions exist. Now find them all.

Step 1: one fraction. Over the common bottom $9ab$ ,
$\frac{a}{b} + \frac{14b}{9a} = \frac{9a^2 + 14b^2}{9ab}.$
This is a whole number exactly when $9ab$ divides $9a^2 + 14b^2$ . In particular each of $b$ , $a$ and $9$ must divide the top.

Step 2: what can $b$ be?

$b$ divides $14b^2$ , so for $b$ to divide the top it must divide $9a^2$ .
$b$ shares no factor with $a$ , so it shares none with $a^2$ . So $b$ must divide $9$ : $b$ is $1$ , $3$ or $9$ .
Also $9$ divides $9a^2$ , so $9$ must divide $14b^2$ . Since $14$ has no factor $3$ , $b^2$ must be a multiple of $9$ , so $b$ is a multiple of $3$ .
That leaves $b = 3$ or $b = 9$ .

Step 3: what can $a$ be? In the same way, $a$ divides $9a^2$ , so $a$ must divide $14b^2$ . It shares no factor with $b$ , so $a$ divides $14$ : $a$ is $1$ , $2$ , $7$ or $14$ .

Step 4: test the $2 \times 4 = 8$ pairs.

$b = 9$ : the expression is $\frac{a}{9} + \frac{14}{a}$ . For $a = 1, 2, 7, 14$ this is $\frac19 + 14$ , $\frac29 + 7$ , $\frac79 + 2$ , $\frac{14}{9} + 1$ . The part $\frac{a}{9}$ is never whole and the other part is, so none work.
$b = 3$ : the expression is $\frac{a}{3} + \frac{14}{3a}$ .

$a$	1	2	7	14
value	$\frac13 + \frac{14}{3} = 5$	$\frac23 + \frac{7}{3} = 3$	$\frac73 + \frac{2}{3} = 3$	$\frac{14}{3} + \frac13 = 5$

All four work.

So the pairs are $(1,3)$ , $(2,3)$ , $(7,3)$ , $(14,3)$ : four in all.

The answer is $\boxed{\textbf{(A)}\ 4}$ .

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 $a$ and divides $9a^2$ , it must divide $9$ . That shrinks an endless search to a few candidates you can check by hand.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

Combine the fractions:
$\frac{a}{b} + \frac{14b}{9a} = \frac{9a^2 + 14b^2}{9ab}.$
This is an integer exactly when $9ab \mid 9a^2 + 14b^2$ . Extract consequences using $\gcd(a,b) = 1$ .

Bound $b$ . From $b \mid 9a^2 + 14b^2$ we get $b \mid 9a^2$ , and since $b$ is coprime to $a$ , $b \mid 9$ . Also $9 \mid 9a^2 + 14b^2$ gives $9 \mid 14b^2$ , so $3 \mid b$ . Thus $b \in \{3, 9\}$ .

Bound $a$ . From $a \mid 14b^2$ and coprimality, $a \mid 14$ , so $a \in \{1, 2, 7, 14\}$ .

Case $b = 9$ . The condition becomes $81a \mid 9a^2 + 1134$ , so $9 \mid a^2 + 126$ , which needs $3 \mid a$ . No divisor of $14$ works.

Case $b = 3$ . The condition becomes $27a \mid 9a^2 + 126$ , i.e. $3a \mid a^2 + 14$ . Each $a \in \{1, 2, 7, 14\}$ is coprime to $3$ and divides $14$ , and $a^2 + 14 \equiv 1 + 2 \equiv 0 \pmod 3$ , so all four work. Directly:
$\tfrac13 + \tfrac{42}{9} = 5,\quad \tfrac23 + \tfrac{42}{18} = 3,\quad \tfrac73 + \tfrac{42}{63} = 3,\quad \tfrac{14}{3} + \tfrac{42}{126} = 5.$

The pairs are $(1,3), (2,3), (7,3), (14,3)$ : four in all.

The answer is $\boxed{\textbf{(A)}\ 4}$ .

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)